計算機網絡可靠性研究的現狀與展望

摘 要：參考國內外相關文獻，對計算機網絡可靠性研究的現狀進行系統歸納和總結，在此基礎上提出今后急需解決的關鍵性問題。

關鍵詞：計算機網絡；網絡可靠度；綜述

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1674-7712 （2014） 06-0000-01

隨著用戶對計算機網絡的使用，人們對網絡的可靠性要求也越來越高。一旦計算機網絡發生故障，將會對人們的生活、經濟、環境、衛生、及社會安全造成重大甚至是災難性的影響[1]。因此，網絡可靠性的研究具有重大意義和應用價值。

一、研究現狀

計算機網絡可靠性問題的研究最早可追溯到1955年Mr.Lee對電信交換網絡的探索[2]。早期的計算機網絡可靠性研究主要集中在通信網絡領域。20世紀90年代以來，隨著計算機網絡化進程的加快和普及，網絡系統可靠性逐漸成為可靠性領域的研究熱點。與此同時，由于電力網絡、電路網絡、交通網絡、運輸網絡、物流網絡等都涉及到計算機網絡可靠性評估問題，計算機網絡可靠性研究受到越來越多的關注。

（一）網絡可靠度的精確計算

由于網絡可靠度的求解是NP難題，精確計算方法一般只適用于小型、中小型網絡或具有特殊拓撲結構的網絡。目前為止，常見的網絡可靠度精確計算方法有：狀態枚舉法[2]、容斥原理法[3]、不交積和法[4]、因子分解法[5]、狀態空間分解法等[6]。由于網絡可靠度評估是NP難題，上述精確算法一般多用于求解小型網絡或具有特殊拓撲的網絡的可靠度；對于中大型網絡，常用近似算法來求取網絡可靠度。

（二）網絡可靠度的近似計算

近似算法求網絡可靠度是一種以犧牲可靠度精度而降低計算難度的方法。常見的網絡可靠度的近似算法有上下界法、圖變換法、模擬法等。目前，提高網絡可靠度評估精度的同時降低算法復雜度是使用近似算法求解網絡可靠度的研究重點之一。

1.上下界法

上下界法求網絡可靠度的主要思想是通過求出網絡的上下邊界值來近似網絡可靠度的精確值。針對串并聯系統，Djerdjour和Rekab通過不斷地放大約束來求網絡可靠性的上界值[7]；針對gamma網絡，Gunawan則通過對網絡結構進行簡化來求網絡可靠度的下界值[8]。

2.圖變換法

圖變換法計算網絡可靠度的基本思想是按照某種規則簡化網絡后再進行可靠度計算。典型的圖變換法有△-Y型簡化法、串并聯簡化法、多邊形-鏈簡化法和三角形簡化法等。圖變換法可以解決串并聯網絡、gamma網絡等具有特殊拓撲結構的網絡可靠度計算問題，但并不能很好地對其他網絡進行結構簡化。

3.模擬法

模擬法是通過仿真技術來近似計算網絡可靠度，主要包括蒙特卡羅法（Monte-Carlo），智能算法（如蟻群算法、遺傳算法、模糊遺傳算法、神經網絡算法、禁忌搜索算法、模擬退火算法）等。

二、結束語與展望

上述國內外的研究盡管數量不少，也取得了一些成果，但在以下幾個方面還存在諸多問題，有待進行更加深入的研究：

1.現階段，大部分網絡可靠性評估是針對數據通過不相交路徑進行傳輸的基礎上進行研究的，而很少考慮數據通過相交路徑進行傳輸的可靠性評估問題。

2.目前國內正在實施的光纖入戶計劃是在原有輸電線路網絡結構的基礎上鋪劃光纖，因此有必要在滿足費用約束下，針對拓撲結構固定的網絡進行傳輸線優化配置，解決網絡可靠度最大化的傳輸線鋪劃問題。

3.在數據通過相交路徑進行傳輸的可靠性評估方面，已有研究大多采用遍歷算法針對各數據來依次判斷每個網絡容量狀態是否能成功傳輸該數據。對于中大型網絡，釆用遍歷算法來找出各數據對應的網絡容量狀態的效率低下。因此，今后的研究重點之一是提出一種算法來直接求出各數據對應的網絡容量狀態。

4.在多態網絡建模方面，已有研究大多采用的是離散模型建模，即認為網絡的狀態有多種，每種狀態對應一個概率分布。采用離散模型對多態網絡建模獲得了不少應用，但在實際生活中，不少網絡的狀態是連續變化的，因此用連續模型對多態網絡建模并進行相關可靠性分析是未來的一個重要研究方向。

參考文獻

[1]滕云微.網絡可靠性分析系統的設計與實現[J].計算機信息，2008（06）：129-131.

[2]陳育斌，李建東，陳家模.計算通信網絡整體概率連通性的一種新算法，通信學報，2000（09）：91-96.

[3]K.Dohmen，Inclusion-exclusion and network reIiability.The Electronic Journal of Combinatorics，1998（05）：1-8.

[4]吳俊，段東立，趙娟，李俊，鄧宏鐘，潭躍進.網絡系統可靠性研究現狀與展望[J].復雜系統與復雜性科學，2011（02）：77-86.

[5]L.B.Page，J.E. Perry，Reliability of directed networks using the factoring theorem.IEEE Transactions on Reliability，1989（05）：556-562.

[6]P.Doulliez，E.Jamoulle，Transportation networks with random arc capacities.RAIRO，1972（03）：45-60.

[7]M.Djerdjour，K.Rekab，A branch and bound algorithm for designing reliable systems at a minimum cost.Applied Mathematics and Computation，2001（118）：247-259.

[8]Gunawan，Redundant paths and reliability bounds in gamma networks.Applied Mathematical Modelling，2008（04）：588-594.