通信網絡拓撲可靠性層次與測度研究

摘 要：梳理討論了目前通信網絡可靠性研究之間的層次關系，討論了拓撲可靠性所處的地位、任務、指標等。其次，分析了拓撲可靠性的非概率測度，指出了連通度的核心作用。再次，研究了基于邊連通度與節點連通度進行可靠性評價的思想與算法。最后，通過一個算例展示了通信網絡拓撲可靠性評價的具體過程。

關鍵詞：通信網路 可靠性 層次 測度

中圖分類號：TN93 文獻標識碼：A 文章編號：1672-3791（2013）07（c）-0003-02

隨著通信、信息、網絡技術的高速發展與廣泛應用，人們對通信網絡的依賴愈加明顯，隨之而來的可靠性問題日益成為用戶關注的焦點領域。現代通信網絡是一個復雜系統，融合了多學科領域，因此對其可靠性的研究是一項系統工程。

從目前的公開文獻來看，通信網絡可靠性研究分布于網絡應用的各個層次與領域，一般可對應于OIS（Open System Interconnect）系統模型的劃分。同時，通信網絡的復雜性、動態性、多態性等屬性為可靠性評估與優化提出了新的挑戰，導致了研究的視角與側重點也不盡相同。拓撲結構是通信網絡的核心特征，其依據拓撲來組織網絡形態，進而體現通信網絡系統的整體性。因此，對通信網絡拓撲可靠性的研究處于整個通信網絡可靠性研究的中心地位。

1 通信網絡可靠性研究的層次體系

1.1 拓撲可靠性處于核心地位

如引言中所述，拓撲可靠性并不能完全表征整個通信網絡的可靠性，其研究對象只關注于網絡的拓撲結構，忽略了網絡通信設備、路由策略、承載業務、管理效率等因素所帶來的可靠性變化。拓撲層高于設備層，同時是路由層、業務層等高層可靠性的基礎，在整個通信網絡可靠性中處于承上啟下的中間環節，其影響可見一斑。

通信網絡可靠性可分層討論，每層均應設計相應的指標與測度方法，以完成對通信網絡可靠性的定量描述。因此，通信網絡可靠性應具備一個同向、協調、完備的指標體系。在對目前文獻梳理的基礎之上，可得可靠性指標體系。同時，各文獻對可靠性的理解與劃分具有相互重疊性，而且關于同一類指標的描述也不盡相同，新的指標也不斷被提出。

1.2 拓撲可靠性指標分析

在網絡拓撲可靠性的指標描述上是想通的，即在抗毀性與生存性上具有廣泛共識。同時可見，連通度是兩者的指標與測度設計的基礎因素。

（1）網絡拓撲抗毀性。主要用于刻畫在確定的網絡組織結構（即網絡拓撲）、預定的破壞（攻擊）方案下，通信網絡依然能夠保持全網或部分連通（物理可達）的能力。在對實際網絡進行拓撲抽象之后，抗毀性指要破壞（中斷）部分網絡節點連接需要移除（破壞）的最少網絡節點或鏈路（邊）的數目，從而表征出破壞整個或部分通信網絡的困難程度。可見，抗毀性完全由網絡拓撲結構所決定，是可靠性的一個確定型指標。

（2）網絡拓撲生存性。生存性最顯著的變化是引入了網絡部件的失效（故障）概率，用于刻畫在隨機故障或蓄意破壞之下，保持通信網絡整體或部分連通的概率。其建立在圖論與概率論基礎之上的可靠性分析，不僅受網絡拓撲結構的影響，同時還依附于網絡部件（設備）的故障概率與模式、網絡維修與管理等因素，因此網絡拓撲生存性是廣義的拓撲層可靠性。

2 基于連通的通信網絡拓撲可靠性測度

通信網絡拓撲可靠性問題可抽象為圖的可靠性問題，用圖G（V，E）來描述拓撲結構。其中，V表示網絡中節點的集合，例如用戶終端、服務端、路由服務器等；E表示連接網絡中節點的邊（鏈路）集合。同時，本節主要討論拓撲可靠性的非概率（靜態）測度，即不考慮上層業務或下層設備影響，將問題視角完全限定在拓撲層面。

目前，關于拓撲可靠性的靜態測度研究很多，可謂仁者見仁，測度設計的側重點各不相同。例如：連通度（vertex connectivity）、堅韌度（toughness）、完整度（integrity）、粘連度（tenacity）、離散數（scattering number）、膨脹系數（expansion coefficient）等。其中，連通度是拓撲的基礎指標，后續的測度均建立在對連通性的充分考慮的基礎之上。因此，本節以連通度為重點展開討論。

2.1 邊連通度與節點連通度的定義

（1）邊連通度。

記為，其大小等于使網絡成為不連通圖所需去掉鏈路（邊）的最少條數。它反映網絡節點間的內聚程度，是網絡可靠性的一個基本度量指標。例如：通過分析可知，所示的網絡分割至少需要移除3條邊，即邊連通度。

（2）節點連通度。

也成為點連通度，記為，其大小等于使網絡成為不連通圖所需去掉的節點的最少個數。同理，網絡的連通度。從某種意義上講，點連通度是比邊連通度更重要的網絡可靠性度量指標，這是因為在網絡中去掉某個節點就意味著與之關聯的所有鏈路將失去意義。

2.2 邊連通度與節點連通度的算法

（1）算法的基本思想。

通常，要求給定網絡的邊連通度，需要首先確定任意不同兩點的鏈路割集。設和是的兩個不同節點，所謂的一個鏈路割集是指這樣的鏈路集合：若去掉其中所有鏈路，網絡將被分割成兩個分支，一個包含節點；另一個包含節點。假設是中所有鏈路割集中鏈路的最小數，則就是切斷和之間所有路由所需從中刪去的最小鏈路數，故網絡的邊連通度可按（1）式計算：

2）網絡邊連通度計算步驟。

由前所述，計算網絡邊連通度的算法思路是：先按標號算法求分離任兩點的最小鏈路數，然后，再求所有這些數的最小數即可。但是，上述求的算法是針對有向圖給出的，而網絡邊連通度是針對無向圖的，因此，算法需首先將原無向網絡轉換成等效的有向網絡。具體計算步驟如下：

第1步：對給定網絡，任選一對節點和，按下面的步驟求分離和的最小鏈路數：

①首先將轉換成有向圖。方法是：將鏈路集中以為端點的鏈路轉換成中以為起點的到相應節點的有向鏈路，將中以為端點的鏈路轉換成中從相應節點到節點的有向鏈路，又將中其他鏈路轉換成中2條有向鏈路和。

②用標號算法，求中分離與的最小鏈路數。

第2步：對所有節點對，，重復上述步驟計算，最后計算：，即網絡的邊連通度。需要注意的是：由于，對于含有個節點的圖，第2步中需要計算的共有個。

3）網絡節點連通度計算步驟。

算法的思路是：將割點問題轉換成割邊問題，從而使求網絡節點連通度的問題轉換成求網絡的邊連通度問題。轉換的方法是：在網絡中任選一對節點和，首先，類似于邊連通度算法一樣，將轉換成有向網絡，然后，再將構造另一個有向圖，構圖規則是：將中除和外的每個節點拆成2個新的中的節點和，并用中的有向鏈路將它們連接起來。將中每一鏈路換成中的鏈路，并把標為，標為。

由構圖規則可知，在新的網絡中，從發點到收點的包含節點的一條路由，必定包含一個頂點拆成的兩部分之間的那條弧。并且原圖的一對相鄰點及其間的邊被轉換成等效的由4個節點組成的“8”字形有向回路。因此，一個鏈路割集在切斷中到的所有有向路由方面，與在原始無向圖中去掉節點割集有相同作用，即中等于中。綜上，可得網絡節點連通度算法計算步驟如下。

第1步：對原網絡的任一節點對和，按上述規則構造新的有向網絡，并用標號法求中分離和的最小鏈路數，即中分離和的最小割點集點數。

第2步：對所有節點，計算，即得的邊連通度。

3 結論

本文討論了通信網絡可靠性的層次劃分與影響因素，針對性的分析了拓撲層可靠性的指標與測度，指出了“連通度”作為拓撲層可靠性基礎測度，以及其對其它測度設計的重要性。同時，詳細分析了節點連通度與邊連通度的計算思想與算法步驟。最后，通過一個相對簡單的算例演示了通過邊與節點連通度計算來評價某一通信網絡拓撲可靠性的主要流程。

參考文獻

[1]羅鵬程，金光，周經倫.通信網可靠性研究綜述[J].小型微型計算機系統，2000，21（10）：1073-1077.

[2]陳建國.通信網絡拓撲抗毀性評估算法研究[J].通信系統與網絡技術，2006，32（1）：6-7.

[3]饒育萍，林競羽，周東方.網絡抗毀度和節點重要性評價方法[J].計算機工程，2009，35（6）：14-16.