基于啟發式算法的網絡可靠性分配方法

李瑞瑩 任武越

（北京航空航天大學 可靠性與系統工程學院，北京 100191）

基于啟發式算法的網絡可靠性分配方法

李瑞瑩 任武越

（北京航空航天大學 可靠性與系統工程學院，北京 100191）

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

網絡;可靠性;啟發式算法;二分搜索法

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

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

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

為此，本文在AGREE方法的基礎上，根據網絡可靠性與部件可靠性的函數關系確定網絡部件重要度，運用二分搜索法確定基于重要度和復雜度的部件可靠性分配結果，并通過啟發式算法逐步迭代實現網絡k/N端可靠性分配結果的收斂，可有效支持網絡系統開展可靠性分配工作.

1 基本參數

網絡可靠性是指網絡在規定條件下和規定時間內，完成規定功能的能力.對網絡而言，最重要的就是網絡連通功能.連通可靠性［7］成為網絡的重要指標，其表示網絡在規定條件下和規定時間內的連通能力.

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

其中，k/N 端可靠度［8］表示網絡 G（V，E）在規定條件下和規定時間內，節點子集N（含n個節點）中至少k個節點之間能連通的概率（其中，N?V;2≤k≤n）.k/N端可靠度可表示為

式中，Rk/N（t）是t時刻網絡G（V，E）的k/N端可靠度;ξk/N是節點子集N中能相互連通的節點個數少于k前的工作時間;t是網絡規定的時間.

特殊地，當k=n時，k/N端可靠度就是K端可靠度，表示網絡中指定節點子集K中所有節點之間保持連通的概率;當N=V，且k=n時，k/N端可靠度就是全端可靠度，表示網絡中所有節點之間保持連通的能力;當n=2時，k/N端可靠度就是兩端可靠度，表示網絡中兩個指定節點之間保持連通的能力.也就是說，K端可靠度、全端可靠度和兩端可靠度都是k/N端可靠度的特殊情況.

2 算法

2.1AGREE分配法

AGREE分配法根據各單元產品的重要程度、復雜程度進行可靠性指標分配的方法.AGREE方法僅適用于由若干串聯的分系統組成的系統，而分系統內部可以由串聯、并聯、旁聯、n中取r等各類關系的部件組成.假設部件的壽命服從指數分布，具體的分配方法如下:

式中，ti為第i個部件的工作時間;Ci為第i個部件的復雜度:

其中，N為整個系統的基本構成單元個數;ni為第i個部件的基本構成單元個數.

ωi為第i個部件的重要度，反應了第i個部件故障影響任務完成的程度:

其中，Ii表示由于第i個部件故障引起系統故障的次數;Fi表示第i個部件故障的次數.

2.2 AGREE分配法的改進

AGREE分配法體現了可靠性分配的2個基本原則:①對復雜程度高的部件，分配較低的可靠性指標;②對重要度高的部件，分配較高的可靠性指標.

由于網絡一般無法表示為串聯結構，故而無法直接使用式（2）實現可靠性分配.這里仍然假設網絡中各個部件的壽命均服從指數分布，為了體現AGREE分配法的2個基本原則，要求:

在網絡對象上實現基于式（5）的可靠性分配，需要解決兩個問題:一是如何確定網絡部件的重要度;二是如何得出部件的分配結果.

對問題一，由于式（4）表達的重要度計算公式是基于統計數據的，無法解析計算，這里運用文獻［2］中使用的概率重要度:

上式反映了部件可靠度變化對系統可靠度的影響.

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

1）應用狀態枚舉法、容斥原理、不交積和、因子分解等方法［9］確定網絡系統可靠性與部件可靠性的函數關系 Rs=f（R1，R2，…，Rn）;

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

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

3 案例

下面以中國教育網（CERNET，China Education and Research Network）骨干網為例進行可靠性分配，CERNET骨干網拓撲結構如圖1所示.

圖1 CERNET骨干網拓撲結構

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

首先運用狀態空間枚舉法，確定網絡系統可靠性與部件可靠性的函數關系:

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

表1 CERNET骨干網節點可靠性分配迭代結果

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

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

分配完成后，應用 Rs=f（R1，R2，…，Rn）計算出網絡可靠度隨時間的變化關系如圖3所示.由于迭代過程中始終需要滿足R*s≤f（R1，R2，…，Rn），故而網絡在運行1 a時間后75%骨干網節點的連通可靠度至少達到0.95的指標要求必然可以達到.

迭代終止條件ε的選取對分配效率和分配精度有影響.ε越小，所需迭代次數越大，計算時間越長.當ε小到某種程度時，迭代次數和計算時間會迅速增加，如表2所示.

圖3 CERNET骨干網可靠度隨時間變化情況

表2 ε取值對迭代次數的影響

這里的計算時間是由MATLAB程序執行得來的.同時，表2的結果還反映出，在本案例中迭代終止條件ε的選取對本文提出的啟發式算法的收斂性不產生影響.

當網絡可靠性要求值不同時，各節點的分配結果不同，如圖4所示.由于北京節點的重要性，隨著網絡可靠性指標要求的下降，北京節點可靠度分配結果的下降幅度遠小于其他節點.

圖4 CERNET骨干網可靠性指標不同時的分配結果

4 結束語

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

本算法的適用條件為:①網絡部件壽命服從指數分布;②能夠獲得網絡系統可靠性與部件可靠性的函數關系式.

通過CERNET案例研究，實現了對網絡75%節點連通可靠性的分配.隨著迭代次數增多，均方誤差逐漸減小，表現出良好的收斂性.

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

（References）

［1］康銳，石榮德，李瑞瑩.型號可靠性維修性保障性技術規范:第2冊［M］.北京:國防工業出版社，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］王洪德，馬云東.基于網絡模型的通風系統可靠性分配方法研究［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］郭浩.基于體系結構的C4ISR系統可靠性建模及分配方法研究［D］.長沙:國防科技大學信息系統與管理學院，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.算法設計［M］.張立昂，屈婉玲譯.北京:清華大學出版社，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">網絡出版時間:

時間:2012-02-21 11:47;

CNKI:11-2625/V.20120221.1147.021

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

北京市自然基金資助項目（4113074）

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

（編 輯:婁 嘉）