通信網絡拓撲結構分析研究

導言：作為寫作愛好者，不可錯過為您精心挑選的1篇通信網絡拓撲結構分析研究，它們將為您的寫作提供全新的視角，我們衷心期待您的閱讀，并希望這些內容能為您提供靈感和參考。

通信網絡拓撲結構分析研究:通信網絡拓撲可靠性層次與測度研究

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

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

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

從目前的公開文獻來看，通信網絡可靠性研究分布于網絡應用的各個層次與領域，一般可對應于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 節點移動模型和鏈路有效性

1.1 節點移動模型

分析網絡節點的移動方式與性能分析有關，目前的節點移動模型多是從速度和時間角度來進行的，通過節點移動的速度和時間來判斷節點移動對網絡性能的影響。由于實際上的無線移動通信網絡中的節點移動是非常復雜的，為簡化流程，我們假定其處于較為理想的傳輸環境，采用簡單的二維隨機移動模型來進行節點的移動分析。

在一個無邊界限制的二維平面上，節點處于無序移動狀態，在一個基本單位時間里，節點的移動速度是相同的，在進入另一個基本時間單元時方改變速度。所以，節點在X軸和Y軸方向的方向移動中的速度和位移量都呈現出零均值正態分布，所以，節點在時間n的坐標為：

1.2 鏈路有效性

對于某覆蓋半徑為R的節點來說，其他節點與該節點存在鏈路都必須滿足r≤R的條件，否則的話就不存在鏈路關系。在一個無邊界限制的二維平面上，其節點的密度為ξ/，那么半徑為ρ的圓周中的節點密度為：fρ（ρ）=2πξρ。在進行節點的鏈路有效性測試時，就可以將該節點所覆蓋的范圍內所有節點在某時刻鏈路中仍存在的平均節點數與總節點數的比值作為該節點的有效性測試結果。

2 仿真分析

無線移動通信網絡拓撲中的節點移動速度是有一定的限值的，我們最大的位移定義dm為：P{│Δx│>dm}=P{│Δy│>dm}≤ε，任何一個節點密度都存在σ=Kdm，本文將節點的密度定義為0.00135/，得出的K值為1/3。

2.1 鏈路有效性測試

為了確保仿真結果的準確性，進行多次仿真繪制仿真曲線，對覆蓋范圍的所有節點移動狀況進行10000次仿真，然后繪制出仿真曲線圖。

分析節點初始位置對鏈路有效性的影響，圖1中的三條仿真曲線分別是節點初始位置為4、8、10m時的仿真結果。從圖中可以明顯看出，隨著時間的推移，節點的鏈路有效性逐漸降低，當n=200時，三條仿真曲線的鏈路有效性相差不大，接下來的遞減速度也放緩。n在0-50范圍內時，不同初始位置的節點鏈路有效性隨著時間的遞增而迅速降低。到n=100以后，不同初始位置的節點鏈路有效性隨著時間的推移遞減的速度放緩。這說明初始位置對鏈路有效性的影響在節點移動的剛開始一段時間，節點移動的時間長了之后，初始位置對鏈路有效性的影響逐漸變小。

2.2 拓撲結構有效性

假定場景的節點密度為1/，dm為4，改變覆蓋半徑R的大小進行仿真分析。如圖3所示為覆蓋半徑為4、8、16、32、64m時的仿真曲線圖，隨著節點移動時間的推移，拓撲結構的有效性也在降低。覆蓋半徑越大，拓撲結構的有效性越高，遞減的幅度也越小。覆蓋半徑為4、8m時，拓撲結構有效性在節點剛開始移動是呈現急劇降低現象，到n=50后，拓撲結構的有效性降低速度放緩。

3 結束語

無線移動通信網絡作為當前以及未來的主要網絡形式，其拓撲的有效性關系到網絡運行的穩定和安全。拓撲圖中節點的無序移動會影響到網絡的有效性，本文以理想狀態下的網絡運行環境為背景建立了二維平面節點移動模型，經過仿真分析，研究節點初始位置、節點覆蓋半徑大小、節點密度等對拓撲的有效性的影響，而現實環境中的網絡拓撲受到的外界干擾更多，其拓撲有效性還有待進一步研究。

通信網絡拓撲結構分析研究:基于遺傳算法的通信網絡拓撲優化研究

摘要:該文通過分析通信網絡中的拓撲優化問題,抽象出數學模型,并利用遺傳算法對該模型進行求解。最后通過實例驗證用遺傳算法求解該問題明顯優于一些傳統的算法,文中所建立的數學模型和算法能夠正確地解決通信網絡拓撲優化問題。

關鍵詞:遺傳算法;通信網絡;拓撲;優化

隨著信息化的發展,通信網絡不斷擴充新功能,發展新業務。這必然導致網絡規模日益龐大,節點眾多,并且網絡拓撲的結構也越來越復雜。從而造成了數據信息的轉接次數增多,遲延增加,維護難度增大,這就給現代通信網絡的建設和管理提出了新的挑戰。

對通信網絡進行優化能夠使其更加快速有效可靠地傳遞信息,避免和最大限度減少因網絡中斷或延遲帶來的損失。遺傳算法(GA)模擬自然進化過程,是一種具有并行特征的搜索算法,它能對解空間進行搜索,加快對解的搜索速度,便于推廣到多結點的網絡優化設計中,是解決大規模網絡優化問題的有效工具。

1 遺傳算法求解過程

遺傳算法(GA)的主要特點是直接對結構對象進行操作,具有內在的隱含并行性和更好的全局尋優能力,自動獲取和指導優化的搜索空間,自適應調整搜索方向,不需要確定的規則。

使用遺傳算法求解通信網絡的拓撲優化一般采用如圖1的過程。

2 算法設計

2.1 編碼和初始化種群

對于一個n結點的網絡,其G圖最多有n(n-1)/2條邊,所以染色體的長度可定長為n(n-1)/2的二進制串。由于鄰接矩陣具有對稱性,因此只需使用該矩陣的上三角表示,這樣可以使個體的長度為n(n-1)/2,壓縮比為2。 所求問題可用圖2的下(上)三角矩陣表示,稱其為G的鄰接矩陣T。如圖2。

圖2 G的鄰接矩陣T

在上述編碼方式中,則基因型可設為A[1,…,n(n-1)/2],由此可以生成W個基因個體,每個基因個體都是此通信網絡的一種拓撲。

2.2 根據個體適應度進行選擇

求解網絡優化的數學模型屬于求解目標函數最小值問題,適應度函數可設為

隨著進化代數的增加,個體適應度之間的差別越來越小,可以對適應度函數增加一個比例系數a將其放大,f’(x)=af(x),a>1。

2.3 算法終止條件

當種群滿足以下三個條件之一時算法終止并輸出最優解。

1) 個體的最大適應度超過預先設定參數。

2) 個體的平均適應度超過預先設定參數。

3) 種群代數超過預先設定參數。

3 實驗及結果分析

某通信主干網絡節點數為9,經過多次實驗后,選取POP=60,Pc=0.65,Pm=0.01, 并以最大代數max gen=3000做為程序的終止條件。其各節點間線路代價如表1所示。

經過該算法可得到計算結果如圖3。

若采用枚舉法,則時間復雜度為O(2N),此算法時間復雜度為O(N2),所以在對通信網絡優化的同時,大大降低了時間復雜度。

4 結論與總結

通信網絡的優化是一個復雜且涉及范圍廣泛的課題,是通信網絡技術中不可缺少的部分。與遺傳算法相比,傳統算法比較復雜,局限性很大且計算時間較長。本文使用遺傳算法較好地解決了通信網絡優化問題。本文提出的算法對小規模通信網絡的拓撲優化問題能夠較好的求解,對大規模網絡拓撲進行優化還存在不足。改進方法可以在遺傳算法中融合其它優化算法,構成一種混合遺傳算法。本文中對遺傳算法在網絡優化中的研究只進行了初步的探討,要將這種方法完善還需要做進一步探討和研究。