通信網(wǎng)可靠度的近似評估算法設計

1、通信網(wǎng)可靠度的近似評估算法設計摘要：通信網(wǎng)可靠度評估為網(wǎng)絡設計人員提供可靠性設計依據(jù)，而近似評估算法能快速計算出可靠度的邊界值。今天的通信網(wǎng)，尤其是主干網(wǎng)絡，承擔著海量數(shù)據(jù)的傳輸，因部件故障導致的通信中斷將給用戶帶來巨大損失。為減少故障風險以及故障發(fā)生時帶來的損失，工程人員在設計通信網(wǎng)時必須著重分析網(wǎng)絡可靠性，通過反復評估可靠性來優(yōu)化網(wǎng)絡結(jié)構(gòu)。這種可靠性需求在承擔關鍵任務的專用網(wǎng)中表現(xiàn)得尤為突出，如果在設計階段未充分考慮各種因素對網(wǎng)絡可靠性的威脅，那么故障發(fā)生時所導致的通信中斷將帶來災難性的后果。譬如，分析氣象監(jiān)測網(wǎng)絡可靠性時，需要充分考慮各種災害天氣對通信設備的破壞，通過采取保護措施來增強網(wǎng)

2、絡的抗毀能力；分析戰(zhàn)術網(wǎng)可靠性時，需要全面考慮各種攻擊帶來的破壞，通過部署故障恢復策略來提高網(wǎng)絡的抗攻擊能力。 本文在網(wǎng)絡可靠度精確算法的基礎上，提出了一種近似評估通信網(wǎng)可靠度的算法：因子分解算法，用這種算法來近似計算通信網(wǎng)可靠度。該評估方法的算法實現(xiàn)簡單，能快速評估出通信網(wǎng)的近似可靠度。關鍵詞：通信網(wǎng)； 網(wǎng)絡可靠度； 因子分解算法Approximate Evaluation Algorithm Design for Communication Network ReliabilityAbstract: The evaluation of communication network reliab

3、ility provides the network designers with basis for reliability design, and the approximate evaluation algorithm can quickly calculate the margin value of the reliability. Currently, communication networks, the backbone networks in particular, are loaded with gigantic data transmissions. Therefore,

4、any break-off coursed by components breakdown will incur enormous losses for the users. To reduce the breakdown risks and its subsequent losses, the communication network designers must focus on analyzing network reliability and optimize the network structure through repeated evaluation. This kind o

5、f reliability becomes more prominent when it comes to the specialized networks dealing with key tasks. During the designing phase, if the threats to the reliability havent been taken into full consideration, it may incur disastrous consequences in the case of communication break-off. For instance, w

6、hen analyzing the meteorological monitor network, damages of communication equipments caused by should be taken into account; and when analyzing tactical networks, factors of various attacks should be considered, and restoring strategies should be adopted to enhance the anti-attack function.Based on

7、 the accurate algorithm for network reliability, this paper proposes an approximate evaluation algorithm-the factoring algorithm to calculate communication network reliability. This evaluation method, which is feasible and easy, can generate quick result of an approximate reliability of the communic

8、ation network.Key words：Communication Network, Network Reliability, Factoring Algorithm目 錄第1章 緒 論11.1 研究的背景及意義11.2 國內(nèi)外研究狀況21.3 本文主要研究內(nèi)容2第2章 通信網(wǎng)可靠性的研究42.1 通信網(wǎng)可靠性一般理論42.1.1 可靠性的定義42.1.2 可靠性的連通性42.1.3 通信網(wǎng)可靠性設計52.2 通信網(wǎng)可靠性的研究方法分析52.2.1 網(wǎng)絡的抗毀性52.2.2 網(wǎng)絡的生存性62.2.3 網(wǎng)絡的有效性62.3 二端網(wǎng)絡的離散概率模型72.4 算法比較92.4.1 解析算法9

9、2.4.2 上下界算法10第3章 通信網(wǎng)的存儲結(jié)構(gòu)設計123.1 圖在程序中的表示123.2 圖的定義與術語123.2.1 圖的定義123.2.2 圖的常用術語143.3 圖的儲存結(jié)構(gòu)163.3.1 數(shù)組表示法163.3.2 鄰接表163.4 圖在程序中的表示173.4.1 點的度表示173.4.2 鄰結(jié)點的表示183.4.3 邊的表示183.4.4 保存網(wǎng)絡的圖結(jié)構(gòu)183.4.5 網(wǎng)絡的儲存過程193.4.6 舉例說明21第4章 網(wǎng)絡可靠度算法設計244.1 網(wǎng)絡可靠度的近似計算方法244.2 因子分解原理244.2.1 因子分解公式（因子定理）244.2.2 因子分解例子254.3 程序流

10、程圖274.4 因子分解在網(wǎng)絡圖中的具體操作284.4.1 因子分解刪除邊操作284.4.2 刪除邊操作程序的實現(xiàn)304.4.3 因子分解收縮邊操作324.4.4 收縮邊操作程序的實現(xiàn)344.4.5 網(wǎng)絡可靠度的計算364.5 近似算法的實現(xiàn)364.6 程序調(diào)試及運行374.7 計算結(jié)果及實驗結(jié)果384.8 綜合比較52結(jié) 論54致 謝55參考文獻56第1章 緒 論1.1 研究的背景及意義隨著計算機技術和通信技術的迅猛發(fā)展，計算機通信網(wǎng)絡將遍及社會生活的方方面面，涉及到政府、企業(yè)、學校、通信、銀行、軍事等諸多領域，小到人們?nèi)粘Ｉ?，大到國家安全穩(wěn)定。如何實現(xiàn)通信網(wǎng)絡高速、可靠、安全的運行時一個

11、不可回避的現(xiàn)實問題。近幾年來，我國通信網(wǎng)絡規(guī)模日益擴大，網(wǎng)上所采用的技術和設備也越來越復雜，容量也更加集中，因此通信網(wǎng)中發(fā)生的故障對電信運營部門和社會生活所造成的影響越來越嚴重。同時社會生活對通信網(wǎng)的依賴程度也越來越高、對通信網(wǎng)可靠性的期望值越來越大，因此通信網(wǎng)網(wǎng)可靠性問題已經(jīng)引起運營部門和用戶的高度重視。在通信網(wǎng)的設計和實施過程中都對其可靠性進行了必要的考慮，在運行過程中隊網(wǎng)絡的維護和管理也都有相應的規(guī)定和方法，但是整個通信網(wǎng)運行的可靠性如何，通信網(wǎng)可靠性的發(fā)展和變化情況如何，卻沒有給出明確的答案，其根本原因是缺乏綜合評價通信網(wǎng)可靠性的指標和圍繞該指標建立的科學的綜合評價方法。因此，建立評價

12、通信網(wǎng)可靠性的綜合指標和評價方法具有十分重要的意義，它有助于我們對通信網(wǎng)的可靠性進行全面的認識，也有助于發(fā)現(xiàn)問題并采取有效的措施提高通信網(wǎng)的可靠性。無論是從滿足社會需求還是從運營者自身利益出發(fā)都具有一定的實際經(jīng)濟價值和現(xiàn)實意義。通信是現(xiàn)代信息社會生產(chǎn)力必不可少的要素和衡量綜合國力的重要標志，是信息社會的命脈。通信網(wǎng)絡是現(xiàn)代社會需要和現(xiàn)代通信技術不斷發(fā)展的必然結(jié)果，它不但為各種信息、多種媒體的共享提供了有效手段，同時也提高了通信質(zhì)量。然而，同現(xiàn)代社會中其他大型復雜系統(tǒng)一樣，通信網(wǎng)絡規(guī)模龐大，行為復雜，這對通信網(wǎng)分析、設計帶來了巨大困難。尤其是通信網(wǎng)絡的結(jié)構(gòu)、功能、規(guī)模各有不同，導致對網(wǎng)絡進行描述

13、和分析的極大困難，其可靠性易受網(wǎng)絡設備、網(wǎng)絡管理、網(wǎng)絡拓撲等的影響，致使通信網(wǎng)的可靠性難以確定。由于人們越來越關心網(wǎng)絡正常工作的能力。所以，通信網(wǎng)的可靠性研究具有重要意義。1.2 國內(nèi)外研究狀況通信網(wǎng)可靠性的研究始于60年代，并由于DARPA對ARPANET的投入而得到真正的關注和發(fā)展。到目前為止，無論在通信網(wǎng)可靠性指標的研究還是在通信網(wǎng)行為建模和行為測度的評估方面都取得了大量成果。目前可靠性研究主要是針對設備冗余度、網(wǎng)絡連通性、網(wǎng)絡生存性等方面進行討論，涉及到的理論有概率論、圖論、運籌學和相應的通信理論等。對于運行中的通信網(wǎng)，網(wǎng)管是提高其可靠性的重要手段。提高網(wǎng)管水平，對網(wǎng)絡實行真正實時、動

14、態(tài)的管理是提高可靠性的有效措施。國外的通信網(wǎng)可靠性研究開始較早，主要集中在網(wǎng)絡拓撲結(jié)構(gòu)的連通性上，研究的是任意兩點和特定兩點之間通信的可能性，以及能夠進行通信的節(jié)點對的數(shù)量。我國在網(wǎng)絡可靠性計算方面的研究較為深入，國內(nèi)許多大學和科研機構(gòu)的眾多學者做了大量工作，取得了豐碩的成果。如有些學者在對網(wǎng)絡全終端可靠性的上下界限的計算問題進行了較為深入的研究和探索，提出了基于斷集的可靠性界的計算方法和節(jié)點失效下全端可靠性的上下界的計算公式。1.3 本文主要研究內(nèi)容本文的研究課題是“通信網(wǎng)可靠度的近似評估算法設計”本文主要是以計算機通信主干網(wǎng)絡為對象來開展研究工作的。主要研究內(nèi)容包括如下幾個方面:（1）通信

15、網(wǎng)可靠性分析模型本文針對計算機通信網(wǎng)絡規(guī)模不斷增長的現(xiàn)實，對通信主干網(wǎng)絡的擴充問題進行了細致的研究，建立了基于全終端可靠度的網(wǎng)絡擴充問題的數(shù)學模型，給出了求解該網(wǎng)絡模型可靠性的算法設計。（2）網(wǎng)絡可靠度近似計算方法盡管缺乏有效的大規(guī)模網(wǎng)絡可靠度計算方法，但是可通過計算一些邊界值來近似網(wǎng)絡的可靠度精確值，本文就是通過找到通信網(wǎng)可靠度的上下界來近似測算研究。（3）網(wǎng)絡結(jié)構(gòu)在計算機內(nèi)的高效存儲網(wǎng)絡好比一個個的圖，有支點和樹干構(gòu)成，現(xiàn)實中網(wǎng)絡有各種拓撲結(jié)構(gòu)，常見的有星形、總線形、環(huán)形和網(wǎng)狀形等。隨機圖是指由網(wǎng)絡拓撲結(jié)構(gòu)轉(zhuǎn)化來的一個圖G=(N, E)，N是圖中點的集合，E是圖中邊的集合,實際中點好比通信

16、終端，邊好比通信線路。根據(jù)特定的模型實現(xiàn)網(wǎng)絡圖在計算機中的存儲。 （4）算法分析與設計通過和傳統(tǒng)方式比較分析，確定一種新型的算法：因子分解算法，來實現(xiàn)對網(wǎng)絡可靠度近似度的高效計算。第2章 通信網(wǎng)可靠性的研究2.1 通信網(wǎng)可靠性一般理論2.1.1 可靠性的定義產(chǎn)品的可靠性曾被定義為“產(chǎn)品在給定條件下和規(guī)定時間內(nèi)完成規(guī)定功能的能力?！鳖愃频目蓪⑼ㄐ啪W(wǎng)可靠性定義為：“在人為或自然的破壞作用下，通信網(wǎng)在規(guī)定條件下和規(guī)定時間內(nèi)的生存能力。”這里最重要的是通信網(wǎng)的規(guī)定功能和生存能力指的是什么。從圖論來看，通信網(wǎng)是由節(jié)點和鏈路組成的，當任何原因造成某些節(jié)點或者鏈路失效時，首先會使全網(wǎng)的連通性變差；其次，由于

17、連通性變差會導致網(wǎng)絡余存部分的性能指標下降。因此，通信網(wǎng)的生存或規(guī)定功能應從連通性和性能指標兩方而考慮。常用的判據(jù)為以下五種: 網(wǎng)絡中給定的節(jié)點對之間至少存在一條路徑；網(wǎng)絡中一個指定節(jié)點能與一組節(jié)點能與一組節(jié)點相互通信；網(wǎng)路中可以相互連通的節(jié)點數(shù)大于某一閾值；網(wǎng)路中任意兩個節(jié)點間傳輸時延小于某一閾值；網(wǎng)絡的吞吐量超過某一閾值。其中前三條是從通信網(wǎng)的連通性考慮的，后三天是從網(wǎng)絡的性能指標考慮的。2.1.2 可靠性的連通性這里研究通信網(wǎng)的可靠性主要是基于網(wǎng)絡拓撲結(jié)構(gòu)，探討當某些節(jié)點或鏈路失效時，網(wǎng)絡能繼續(xù)進行通信的能力。通常是根據(jù)圖論中的連通性來研究的。連通性越好，可靠性越高。下而先用圖論定義兩個

18、參數(shù)和是圖的連通度，它是使圖成為不連通圖至少需要去掉的節(jié)點數(shù)。是圖的結(jié)合度，它是使圖成為不連通圖至少需要去掉的邊數(shù)。對n個點，m條變的連通圖，可證明下式成立： 稱為網(wǎng)的抗毀性，又稱網(wǎng)的冗余度。要求圖的連通性好或通信網(wǎng)的可靠性高，常希望F大一些，因為點數(shù)一定時，邊數(shù)越多，任意兩點之間的路徑越多，邊數(shù)最小的連通圖是樹。此時m=n-1，。即樹中任意兩點之間只有一條路徑，去掉任意一條邊或任意一點，必然使圖變?yōu)椴贿B通圖。2.1.3 通信網(wǎng)可靠性設計通信網(wǎng)的可靠性設計是要在滿足給定的可靠性指標的條件下，尋找最經(jīng)濟的網(wǎng)絡結(jié)構(gòu)。由于影響通信網(wǎng)的可靠性的因素很多，在進行網(wǎng)的可靠性設計時，可以從構(gòu)成網(wǎng)絡部件的可靠

19、性、網(wǎng)絡的拓撲結(jié)構(gòu)、路由選擇方式等方而來考慮。網(wǎng)絡部件的可靠性。通信網(wǎng)是由基本的部件或子系統(tǒng)等構(gòu)成的，提高網(wǎng)的可靠性必須首先盡量降低部件或子系統(tǒng)的故障率。如在進行系統(tǒng)設計時，避免過多部件的串接，對可靠性高的系統(tǒng)采用備份形成并接系統(tǒng)等。網(wǎng)絡的拓撲結(jié)構(gòu)。要想提高通信網(wǎng)的可靠性，從網(wǎng)絡拓撲結(jié)構(gòu)來講即提高連通性，至少應保證任何兩個節(jié)點之間有兩條無共邊的路徑。這是因為在實際中，端局一般維護力量較集中，可靠性較高，傳輸鏈路則是薄弱環(huán)節(jié)，由于近代技術的發(fā)展，傳輸鏈路的可靠度也不會太低，一旦出現(xiàn)故障，也能及時修復，在修復期間另一條邊出故障的概率較小，所以只要任意兩節(jié)點之間有兩條無共邊的路徑即可滿足一定的可靠性

20、。2.2 通信網(wǎng)可靠性的研究方法分析2.2.1 網(wǎng)絡的抗毀性網(wǎng)絡的抗毀性（Invulnerability）描述了通信網(wǎng)在人為破燈，作用下的網(wǎng)絡可靠性，它假定“破壞者具有關于網(wǎng)絡結(jié)構(gòu)的n部資料，并采用一種確定的破壞策略”。對于一個通信網(wǎng)，網(wǎng)絡的抗毀性指出至少需要破壞幾個節(jié)點或幾條鏈路才能中斷部分節(jié)點之間的通信，即指出破壞一個通信網(wǎng)的困難程度。網(wǎng)絡的抗毀性通過兩個可靠性的確定測度粘聚度和連通度來表示。網(wǎng)絡的抗毀性所采用的通信網(wǎng)生存判據(jù)為:網(wǎng)絡中任何一對節(jié)點之間至少存在一條路徑。即僅考慮了網(wǎng)絡的連通性。但對于通信來說，如果一對節(jié)點之間幸存的這條路徑很長（中繼節(jié)點很多)，致使信息傳輸時延達到不可容忍的

21、程度，這條路徑也就沒有多大意義了，此時可以認為這對節(jié)點不連通。 網(wǎng)絡的抗毀性是從圖論的概念中提出來的，它從網(wǎng)絡連通性的角度描述了網(wǎng)絡拓撲結(jié)構(gòu)對通信網(wǎng)可靠性的影響。對于軍用通信網(wǎng)來說，網(wǎng)絡的抗毀性無疑是一項重要的指標。但對于商用通信網(wǎng)而言，由于它被蓄意破壞的可能性很小，網(wǎng)絡的抗毀性也就沒有那么重要了。 網(wǎng)絡的抗毀性與網(wǎng)絡部件的可靠性無關，所以它不能完全描述通信網(wǎng)的可靠性，但它指出了通信網(wǎng)可靠性最重要的一個方面網(wǎng)絡拓撲結(jié)構(gòu)的可靠性。 網(wǎng)絡的粘聚度和連通度可通過圖論算法計算出來，算法在給出數(shù)值指標的同時，還可以指出哪些鏈路和哪些節(jié)點是最關鍵的，它們的失效將影響到整個通信網(wǎng)的生存。2.2.2 網(wǎng)絡的生

22、存性網(wǎng)絡的生存性（Survivability）給出了通信網(wǎng)在隨機性破壞作用下的網(wǎng)絡可靠性。在軍用環(huán)境中，隨機性破壞表現(xiàn)為“破壞者只具有關于網(wǎng)絡結(jié)構(gòu)的部分資料，并采用一種隨機的破壞策略”；在商用環(huán)境中，隨機性破壞則表現(xiàn)為網(wǎng)絡部件（節(jié)點和鏈路）的自然失效。網(wǎng)絡的生存性由可靠性的概率測度連通概率來表示，它給出通信網(wǎng)在一定意義上的連通概率。在網(wǎng)絡生存性的研究中，有一條重要的基本假設是：網(wǎng)絡部件之間是相互統(tǒng)計獨立的。但在實際通信網(wǎng)中，這種假設可能不存在，如無線電通信網(wǎng)中存在著電磁干擾。網(wǎng)絡生存性是基于概率論和圖論的知識提出來的，它描述了隨機性破壞（主要是網(wǎng)絡部件的自然失效）以及網(wǎng)絡拓撲結(jié)構(gòu)對通信網(wǎng)可靠性

23、的影響。這里的可靠性實際上是網(wǎng)絡的連通性，連通性無論對軍用通信網(wǎng)還是商用通信網(wǎng)都是十分重要的，它是通信網(wǎng)最基本的特性。所以，網(wǎng)絡生存性是通信網(wǎng)可靠性領域中研究得最多、持續(xù)時間最長的課題。2.2.3 網(wǎng)絡的有效性無論是網(wǎng)絡的抗毀性還是網(wǎng)絡的生存性，都只從網(wǎng)絡連通性的角度去考察通信網(wǎng)的可靠性，而沒有從網(wǎng)絡的業(yè)務性能（如吞吐量和時延）來研究通信網(wǎng)的可靠性。實際上，通信網(wǎng)的設計者和使用者更關心網(wǎng)絡在失效環(huán)境中的業(yè)務性能。為此，人們提出了網(wǎng)絡的有效性（Availability）基于網(wǎng)絡業(yè)務性能的可靠性測度，它指出了通信網(wǎng)在網(wǎng)絡部件失效條件下滿足通信業(yè)務性能要求的程度。網(wǎng)絡的有效性探討了由于網(wǎng)絡部件失效引

24、起網(wǎng)絡業(yè)務性能下降的問題，使通信網(wǎng)可靠性的測度更面向通信、面向用戶，更具有直觀性，把通信網(wǎng)可靠性的研究工作大大推進了一步。2.3 二端網(wǎng)絡的離散概率模型通信網(wǎng)的可靠性是指將所需要的信息從源節(jié)點成功地送到終結(jié)點的概率。它與網(wǎng)內(nèi)節(jié)點、支柱可靠性、網(wǎng)的拓撲結(jié)構(gòu)及容量有關。為了便于描述和計算，我們用一個圖G(V, E)表示通信網(wǎng)。計算機通信網(wǎng)絡的拓撲類型較多，但最基本的拓撲類型有6種:星狀、樹狀、網(wǎng)狀、環(huán)狀、總線狀和混合狀，如圖所示。 a）星狀 b）樹狀 c）網(wǎng)狀 d）環(huán)狀 e）總線狀 f）混合狀圖2-1 各種網(wǎng)絡拓撲結(jié)構(gòu)符號表示G(V, E)表示二端網(wǎng)絡拓撲結(jié)構(gòu)的圖，V是圖的點集，E是圖的邊集s源端

25、d終端F(t)二端網(wǎng)絡的故障分布函數(shù)R(t)二端網(wǎng)絡的可靠度分布函數(shù)REL(G)離散概率模型下的二端網(wǎng)絡可靠度函數(shù)xi網(wǎng)絡第i個部件的狀態(tài)值（0或者1）x有n個部件的二端網(wǎng)絡狀態(tài)向量，x=(x0, x1 xn-1)fb()網(wǎng)絡狀態(tài)的布爾函數(shù)可靠性工程中，故障分布函數(shù)通常被用來描述系統(tǒng)的可靠性，分析系統(tǒng)的故障率、平均故障時間、故障頻率等可靠性指標。同樣，網(wǎng)絡的故障分布函數(shù)也可用來分析網(wǎng)絡的可靠性，如下是網(wǎng)絡故障分布函數(shù)的一般定義： (2-1)網(wǎng)絡可靠度分布函數(shù)可描述為： (2-2)上述只是網(wǎng)絡故障分布函數(shù)和可靠度分布函數(shù)的簡單描述，作為一個復雜系統(tǒng)，網(wǎng)絡的故障分布是很難描述的。一條鏈路或者一個結(jié)

26、點的故障分布也許比較容易，但從全網(wǎng)的角度去描述故障并不是一件容易的事情。網(wǎng)絡故障的原因很多很復雜，譬如，隨機的單點故障、多點故障、依賴故障、流量擁塞故障等等。而且，當網(wǎng)絡規(guī)模很大時，故障描述會隨著網(wǎng)絡故障數(shù)量的膨脹變得極其困難。從大多數(shù)網(wǎng)絡可靠性文獻來看，離散概率模型是分析網(wǎng)絡可靠性的有效手段，它既簡化了網(wǎng)絡的復雜性，又不失一般性。網(wǎng)絡可靠性的離散概率模型包括隨機圖和部件工作概率分布兩部分。隨機圖是指由網(wǎng)絡拓撲結(jié)構(gòu)轉(zhuǎn)化來的一個圖G=(N, E)，N是圖中點的集合，E是圖中邊的集合，原來網(wǎng)絡中路由器轉(zhuǎn)化成圖中的點，網(wǎng)絡中連接路由器的鏈路轉(zhuǎn)化成圖中的邊，圖中的點和邊有兩種狀態(tài)：工作和故障。部件（點

27、和邊）工作概率分布是指部件工作服從0-1分布，第i個部件可用隨機變量xi表示，xi =1表示部件工作，其概率為Prxi =1；xi =0表示部件故障，其概率為Prxi =0=1Prxi =1。在上述離散概率模型下，可用隨機向量x=(x0, x1, xn-1)來表示n個部件網(wǎng)絡G的狀態(tài)，網(wǎng)絡處于狀態(tài)X的概率可表示為： (2-3)根據(jù)部件工作或故障狀態(tài)，可以得到2n個網(wǎng)絡狀態(tài)，這些狀態(tài)構(gòu)成了網(wǎng)絡狀態(tài)空間。從而有如下布爾函數(shù)： (2-4)這樣，網(wǎng)絡的可靠度可如下表示： (2-5)下面的例子進一步解釋了網(wǎng)絡可靠性的離散概率模型，如圖2-2網(wǎng)絡的邊集和點集分別為，Nv0, v1, v2, v3，E= e

28、0, e1, e2, e3, e4， v0和v3分別是網(wǎng)絡的源端和終端，如果這兩點保持連通就認為網(wǎng)絡可靠。假設結(jié)點可靠，那么可靠性分析只考慮邊的工作概率。令xi表示邊ei的狀態(tài)，其工作概率為pi 。狀態(tài)可以用向量x=(x0, x1, x2, x3, x4)來表示，向量(0,1,1,1,1)表示e0故障 e1, e2, e3, e4工作的網(wǎng)絡狀態(tài)，網(wǎng)絡處于該狀態(tài)的概率可以表示為：網(wǎng)絡的可靠度計算公式為：圖2-2 實例網(wǎng)絡2.4 算法比較2.4.1 解析算法給定網(wǎng)絡S，對任意兩個N點，若弧失效時，這兩個節(jié)點間無路由相通，則稱 為這兩個節(jié)點間的割集。若 是一個割集，則從C中任意除去一條弧后就不是割集

29、，此時稱C為一個最小割集；若 是S的所有割集，=，它表示割集所有的弧 都失效。已知網(wǎng)絡的最小割集，則端對端的連通概率為當輸入節(jié)點與輸出節(jié)點之間的所有最小路已經(jīng)求得，下面給出兩端口之間的可靠度的算法思路。步驟1 挑出長度為n路的全體利用定理化為不交和步驟2 把由集合運算法化為不交和。1）初始化： 2）在f中取一項，使R；3）f，此步利用已知定理進行簡化； 4）f中若還有項，則k=k+1，轉(zhuǎn)B；否則R即為所求。2.4.2 上下界算法1、基本思路設網(wǎng)絡G=（N(G)，(G)），其中N(G)為網(wǎng)絡節(jié)點集，(G)為網(wǎng)絡弧集。1）對于N(G)，運用下述分層算法和分節(jié)點算法分別計算與，并有2）去及，即可求出

30、網(wǎng)絡的最大上限及最小下限。3）網(wǎng)絡的上界可靠度算法依賴于網(wǎng)絡的分層技術。4）符號標記：G表示源節(jié)點到目標節(jié)點的網(wǎng)絡；O表示源節(jié)點代號；n表示目標節(jié)點代號；（a，b）表示從節(jié)點a到節(jié)點b的??；N(G)表示G的節(jié)點集合，N(G)=0，1，2， ，n；(G)：G的弧集合；R(G)表示網(wǎng)絡可靠度，R(G)=節(jié)點O與節(jié)點n連通的概率；X(a，b)表示二進制隨機變量，X(a，b)=1，當且僅當?。╝，b）工作正常；表示?。╝，b）的可靠度，（a，b）(G)，；表示G的第k層次，k=1,2，s（s為網(wǎng)絡的總層次數(shù)）；()表示第k層的可靠度上界，(G)表示網(wǎng)絡G的可靠度上界；表示G中節(jié)點a的可靠度下界；(G)

31、表示G的可靠度下界，(G)（n為目標節(jié)點）；T表示弧集；C表示節(jié)點集。2、網(wǎng)絡上界可靠度算法對于網(wǎng)絡上界可靠度算法，我們要利用深度優(yōu)先遍歷技術對網(wǎng)絡進行分層，其分層要去如下所示。1）每一層為網(wǎng)絡的一個子集，即2）每層均至少含一條從源節(jié)點n到目標節(jié)點O之最小路3）每層為串并聯(lián)結(jié)構(gòu)，從而很容易計算出子網(wǎng)的串并聯(lián)可靠度R()4）有G=，s為分層數(shù)目5）對于任意弧（a，b），下式成立G最終網(wǎng)絡可靠度上界為：(G)3、網(wǎng)絡下界可靠度算法如果A，B，C是三條給定的路，則根據(jù)全概率公式： 為此，我們可以推出下面一個不等式：通過上面的不等式可以計算一個節(jié)點jN的下界可靠度。如果弧收斂于一節(jié)點，則下界可靠度可以

32、通過將具有最大可靠度的弧分成兩條并聯(lián)弧來計算出：可靠度下界算法描述如下：步驟1 設i=0，并且j=1；步驟2 T=；步驟3 如果T集合中的節(jié)點數(shù)等于1，則如果T中的節(jié)點數(shù)是奇數(shù)，則 否則，令MAX并將相應的i賦予x，步驟4 如果j = n則得到下界可靠度，R(G) = ，停止計算；否則，j = j + 1，轉(zhuǎn)步驟2第3章 通信網(wǎng)的存儲結(jié)構(gòu)設計3.1 圖在程序中的表示網(wǎng)絡好比一個個的圖，有支點和樹干構(gòu)成，現(xiàn)實中網(wǎng)絡有各種拓撲結(jié)構(gòu)，常見的有星形、總線形、環(huán)形和網(wǎng)狀形等。隨機圖是指由網(wǎng)絡拓撲結(jié)構(gòu)轉(zhuǎn)化來的一個圖G=(N, E)，N是圖中點的集合，E是圖中邊的集合,實際中點好比終端，邊好比通信線路。根據(jù)

33、故障分類可分為點不可靠和邊不可靠。結(jié)合度是指斷開網(wǎng)絡的兩端所需要去掉的最少鏈路數(shù)目；連通度是指斷開網(wǎng)絡兩端所需要去掉的最少結(jié)點數(shù)目。在本次設計中只考慮邊的不可靠，始終認為點是可靠的。3.2 圖的定義與術語3.2.1 圖的定義圖是一種數(shù)據(jù)元素間為多對多關系的數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型。圖3-1 簡單的網(wǎng)絡圖ADT Graph數(shù)據(jù)對象V ：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R：R=VRVR=|v,w(-V且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息基本操作P：CreateGraph(&G,V,VR);初始條件：V是圖的頂點集，VR是圖

34、中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖GDestroyGraph(&G);初始條件：圖G存在操作結(jié)果：銷毀圖GLocateVex(G,u);初始條件：圖G存在，u一G中頂點有相同特征操作結(jié)果：若G中存在頂點u, 則返回該頂點在圖中位置；否則返回其它信息。GetVex(G,v);初始條件：圖G存在，v是G中某個頂點操作結(jié)果：返回v的值。PutVex(&G,v,value);初始條件：圖G存在，v是G中某個頂點操作結(jié)果：對v賦值valueFirstAdjVex(G,v);初始條件：圖G存在，v是G中某個頂點操作結(jié)果：返回v的第一個鄰接頂點。若頂點在G中沒有鄰接頂點，則返回“空”NextAdj

35、Vex(G,v,w);初始條件：圖G存在,v是G中某個頂點,w是v的鄰接頂點。操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點。若w是v的最后一個鄰接點，則返回“空”InsertVex(&G,v);初始條件：圖G存在，v和圖中頂點有相同特征操作結(jié)果：在圖G中增添新頂點vDeleteVex(&G,v);初始條件：圖G存在，v是G中某個頂點操作結(jié)果：刪除G中頂點v及其相關的弧InsertAcr(&G,v,w);初始條件：圖G存在，v和w是G中兩個頂點操作結(jié)果：在G中增添弧,若G是無向的，則還增添對稱弧DeleteArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個頂點操作結(jié)果：在G中刪除弧,

36、若G是無向的，則還刪除對稱弧DFSTraverser(G,v,Visit();初始條件：圖G存在，v是G中某個頂點，Visit是頂點的應用函數(shù)操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)Visit一次。一旦Visit()失敗，則操作失敗。BFSTRaverse(G,v,Visit();初始條件：圖G存在，v是G中某個頂點，Visit是頂點的應用函數(shù)操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)Visit一次。一旦Visit()失敗，則操作失敗。ADT Graph3.2.2 圖的常用術語圖3-2 有向圖和無向圖對上圖有：G1=(V1,A1)其中：V1=v1,v2,v3,

37、v4 A1=,如果用n表示圖中頂點數(shù)目，用e表示邊或弧的數(shù)目，則有：對于無向圖，e的取值范圍是0到n(n-1)/2,有n(n-1)/2條邊的無向圖稱為完全圖。對于有向圖，e有取值范圍是0到n(n-1)。具有n(n-1)條弧的有向圖稱為有向完全圖。有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。圖3-3 各種圖v1與v2互為鄰接點；e1依附于頂點v1和v2v1和v2相關聯(lián)；v1的度為3圖3-4 度的表示3.3 圖的儲存結(jié)構(gòu)3.3.1 數(shù)組表示法圖的存儲結(jié)構(gòu)：用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關系（邊或?。┑男畔ⅰ? 圖的數(shù)組（鄰接矩陣）存儲表示#define INFINITY

38、 INT_MAX /最大值無窮大#define MAX_VERTEX_NUM 20 /最大頂點個數(shù)typedef enumDG,DN,AG,AN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef struct ArcCellVRType adj; /VRType是頂點關系類型。對無權圖，用1或0表示相鄰否，對帶權圖，則為權值類型InfoType *info; /該弧相關停息的指針ArcCell,AdjMatrixmax_vertex_nummax_vertex_num;tpyedef structVertexType vexsMAX_VERTEX_NUM; /頂點向量AdjM

39、atrix arcs; /鄰接矩陣int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù)GraphKind kind; /圖的種類標志MGraph;圖3-5 鄰接矩陣表示法3.3.2 鄰接表鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點vi的邊（對有向圖是以頂點vi為尾的?。Ｃ總€結(jié)點由三個域組成，其中鄰接點域(adjvex)指示與頂點vi鄰接的點在圖中的位置，鏈域(nextarc)指示下一條邊或弧的結(jié)點；數(shù)據(jù)域(info)存儲和邊或弧相關的信息，如權值等。每個鏈表上附設一個表頭結(jié)點，包含鏈域(firstarc)指向鏈表中第一個

40、結(jié)點，還設有存儲頂點vi的名或其它有關信息的數(shù)據(jù)域(data)。如：表結(jié)點adjvexnextarcinfo頭結(jié)點datafirstarc#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc; /指向下一條弧的指針I(yè)nfoType *info; /該弧相關信息的指針ArcNode;typedef struct VNodeVertexType data; /頂點信息ArcNode *firstarc; /指向第一條依附該頂點的弧的指針VNode,AdjListM

41、AX_VERTEX_NUM;typedef struct AdjList vertices; /圖的當前頂點數(shù)和弧數(shù)int vexnum,arcnum; /圖的種類標志int kind;ALGraph;3.4 圖在程序中的表示3.4.1 點的度表示定義一個結(jié)構(gòu)體，名為dgree_node，其中包含點的度數(shù)，各個點在指針中的位置以及點的可靠度。struct dgree_nodeint dgree;int prtadj;float prob;3.4.2 鄰結(jié)點的表示定義一個結(jié)構(gòu)體，名為adjacent_node，其中包含各個點的編號node_id，前后鏈表的指針位置pre、next以及邊的表示pt

42、r_edge。struct adjacent_nodeint node_id;int pre;int next;int idle;int ptr_edge;3.4.3 邊的表示定義一個結(jié)構(gòu)體，名為edge，其中包含邊的可靠度edgeprob，邊所對應的起點和終點from、to以及用flag標記邊是否被訪問。struct edgefloat edgeprob;int flag;int from,to;3.4.4 保存網(wǎng)絡的圖結(jié)構(gòu)最后把點的度和鄰接點的信息儲存在一張完整的圖結(jié)構(gòu)中struct dgramstruct dgree_node dgr_tabMAX_LEN;struct adjacent_nodeadj_tab3*MAX_LEN;int num;int len_adjtable;int vidle;int stail;struct edge* edge_tab;int num_edge;3.4.5 網(wǎng)絡的儲存過程根據(jù)輸入網(wǎng)絡數(shù)據(jù)創(chuàng)建一個圖結(jié)構(gòu)，保存在diagram中，定義名為diag_create的函數(shù)。該函數(shù)從TXT文檔中讀取圖的信息，儲存點的信息，包括點的度數(shù)，頭指針位置等；儲存邊的