時間：2022-07-26 04:56:30
序論：在您撰寫通信網(wǎng)絡拓撲結構分析研究時，參考他人的優(yōu)秀作品可以開闊視野，小編為您整理的1篇范文，希望這些建議能夠激發(fā)您的創(chuàng)作熱情，引導您走向新的創(chuàng)作高度。
摘 要：梳理討論了目前通信網(wǎng)絡可靠性研究之間的層次關系，討論了拓撲可靠性所處的地位、任務、指標等。其次，分析了拓撲可靠性的非概率測度，指出了連通度的核心作用。再次，研究了基于邊連通度與節(jié)點連通度進行可靠性評價的思想與算法。最后，通過一個算例展示了通信網(wǎng)絡拓撲可靠性評價的具體過程。
關鍵詞：通信網(wǎng)路 可靠性 層次 測度
隨著通信、信息、網(wǎng)絡技術的高速發(fā)展與廣泛應用，人們對通信網(wǎng)絡的依賴愈加明顯，隨之而來的可靠性問題日益成為用戶關注的焦點領域?，F(xiàn)代通信網(wǎng)絡是一個復雜系統(tǒng)，融合了多學科領域，因此對其可靠性的研究是一項系統(tǒng)工程。
從目前的公開文獻來看，通信網(wǎng)絡可靠性研究分布于網(wǎng)絡應用的各個層次與領域，一般可對應于OIS（Open System Interconnect）系統(tǒng)模型的劃分。同時，通信網(wǎng)絡的復雜性、動態(tài)性、多態(tài)性等屬性為可靠性評估與優(yōu)化提出了新的挑戰(zhàn)，導致了研究的視角與側重點也不盡相同。拓撲結構是通信網(wǎng)絡的核心特征，其依據(jù)拓撲來組織網(wǎng)絡形態(tài)，進而體現(xiàn)通信網(wǎng)絡系統(tǒng)的整體性。因此，對通信網(wǎng)絡拓撲可靠性的研究處于整個通信網(wǎng)絡可靠性研究的中心地位。
1 通信網(wǎng)絡可靠性研究的層次體系
1.1 拓撲可靠性處于核心地位
如引言中所述，拓撲可靠性并不能完全表征整個通信網(wǎng)絡的可靠性，其研究對象只關注于網(wǎng)絡的拓撲結構，忽略了網(wǎng)絡通信設備、路由策略、承載業(yè)務、管理效率等因素所帶來的可靠性變化。拓撲層高于設備層，同時是路由層、業(yè)務層等高層可靠性的基礎，在整個通信網(wǎng)絡可靠性中處于承上啟下的中間環(huán)節(jié)，其影響可見一斑。
通信網(wǎng)絡可靠性可分層討論，每層均應設計相應的指標與測度方法，以完成對通信網(wǎng)絡可靠性的定量描述。因此，通信網(wǎng)絡可靠性應具備一個同向、協(xié)調(diào)、完備的指標體系。在對目前文獻梳理的基礎之上，可得可靠性指標體系。同時，各文獻對可靠性的理解與劃分具有相互重疊性，而且關于同一類指標的描述也不盡相同，新的指標也不斷被提出。
1.2 拓撲可靠性指標分析
在網(wǎng)絡拓撲可靠性的指標描述上是想通的，即在抗毀性與生存性上具有廣泛共識。同時可見，連通度是兩者的指標與測度設計的基礎因素。
（1）網(wǎng)絡拓撲抗毀性。主要用于刻畫在確定的網(wǎng)絡組織結構（即網(wǎng)絡拓撲）、預定的破壞（攻擊）方案下，通信網(wǎng)絡依然能夠保持全網(wǎng)或部分連通（物理可達）的能力。在對實際網(wǎng)絡進行拓撲抽象之后，抗毀性指要破壞（中斷）部分網(wǎng)絡節(jié)點連接需要移除（破壞）的最少網(wǎng)絡節(jié)點或鏈路（邊）的數(shù)目，從而表征出破壞整個或部分通信網(wǎng)絡的困難程度?？梢姡箽酝耆删W(wǎng)絡拓撲結構所決定，是可靠性的一個確定型指標。
（2）網(wǎng)絡拓撲生存性。生存性最顯著的變化是引入了網(wǎng)絡部件的失效（故障）概率，用于刻畫在隨機故障或蓄意破壞之下，保持通信網(wǎng)絡整體或部分連通的概率。其建立在圖論與概率論基礎之上的可靠性分析，不僅受網(wǎng)絡拓撲結構的影響，同時還依附于網(wǎng)絡部件（設備）的故障概率與模式、網(wǎng)絡維修與管理等因素，因此網(wǎng)絡拓撲生存性是廣義的拓撲層可靠性。
2 基于連通的通信網(wǎng)絡拓撲可靠性測度
通信網(wǎng)絡拓撲可靠性問題可抽象為圖的可靠性問題，用圖G（V，E）來描述拓撲結構。其中，V表示網(wǎng)絡中節(jié)點的集合，例如用戶終端、服務端、路由服務器等；E表示連接網(wǎng)絡中節(jié)點的邊（鏈路）集合。同時，本節(jié)主要討論拓撲可靠性的非概率（靜態(tài)）測度，即不考慮上層業(yè)務或下層設備影響，將問題視角完全限定在拓撲層面。
目前，關于拓撲可靠性的靜態(tài)測度研究很多，可謂仁者見仁，測度設計的側重點各不相同。例如：連通度（vertex connectivity）、堅韌度（toughness）、完整度（integrity）、粘連度（tenacity）、離散數(shù)（scattering number）、膨脹系數(shù)（expansion coefficient）等。其中，連通度是拓撲的基礎指標，后續(xù)的測度均建立在對連通性的充分考慮的基礎之上。因此，本節(jié)以連通度為重點展開討論。
2.1 邊連通度與節(jié)點連通度的定義
（1）邊連通度。
記為，其大小等于使網(wǎng)絡成為不連通圖所需去掉鏈路（邊）的最少條數(shù)。它反映網(wǎng)絡節(jié)點間的內(nèi)聚程度，是網(wǎng)絡可靠性的一個基本度量指標。例如：通過分析可知，所示的網(wǎng)絡分割至少需要移除3條邊，即邊連通度。
（2）節(jié)點連通度。
也成為點連通度，記為，其大小等于使網(wǎng)絡成為不連通圖所需去掉的節(jié)點的最少個數(shù)。同理，網(wǎng)絡的連通度。從某種意義上講，點連通度是比邊連通度更重要的網(wǎng)絡可靠性度量指標，這是因為在網(wǎng)絡中去掉某個節(jié)點就意味著與之關聯(lián)的所有鏈路將失去意義。
2.2 邊連通度與節(jié)點連通度的算法
（1）算法的基本思想。
通常，要求給定網(wǎng)絡的邊連通度，需要首先確定任意不同兩點的鏈路割集。設和是的兩個不同節(jié)點，所謂的一個鏈路割集是指這樣的鏈路集合：若去掉其中所有鏈路，網(wǎng)絡將被分割成兩個分支，一個包含節(jié)點；另一個包含節(jié)點。假設是中所有鏈路割集中鏈路的最小數(shù)，則就是切斷和之間所有路由所需從中刪去的最小鏈路數(shù)，故網(wǎng)絡的邊連通度可按（1）式計算：
2）網(wǎng)絡邊連通度計算步驟。
由前所述，計算網(wǎng)絡邊連通度的算法思路是：先按標號算法求分離任兩點的最小鏈路數(shù)，然后，再求所有這些數(shù)的最小數(shù)即可。但是，上述求的算法是針對有向圖給出的，而網(wǎng)絡邊連通度是針對無向圖的，因此，算法需首先將原無向網(wǎng)絡轉(zhuǎn)換成等效的有向網(wǎng)絡。具體計算步驟如下：
第1步：對給定網(wǎng)絡，任選一對節(jié)點和，按下面的步驟求分離和的最小鏈路數(shù)：
①首先將轉(zhuǎn)換成有向圖。方法是：將鏈路集中以為端點的鏈路轉(zhuǎn)換成中以為起點的到相應節(jié)點的有向鏈路，將中以為端點的鏈路轉(zhuǎn)換成中從相應節(jié)點到節(jié)點的有向鏈路，又將中其他鏈路轉(zhuǎn)換成中2條有向鏈路和。
②用標號算法，求中分離與的最小鏈路數(shù)。
第2步：對所有節(jié)點對，，重復上述步驟計算，最后計算：，即網(wǎng)絡的邊連通度。需要注意的是：由于，對于含有個節(jié)點的圖，第2步中需要計算的共有個。
3）網(wǎng)絡節(jié)點連通度計算步驟。
算法的思路是：將割點問題轉(zhuǎn)換成割邊問題，從而使求網(wǎng)絡節(jié)點連通度的問題轉(zhuǎn)換成求網(wǎng)絡的邊連通度問題。轉(zhuǎn)換的方法是：在網(wǎng)絡中任選一對節(jié)點和，首先，類似于邊連通度算法一樣，將轉(zhuǎn)換成有向網(wǎng)絡，然后，再將構造另一個有向圖，構圖規(guī)則是：將中除和外的每個節(jié)點拆成2個新的中的節(jié)點和，并用中的有向鏈路將它們連接起來。將中每一鏈路換成中的鏈路，并把標為，標為。
由構圖規(guī)則可知，在新的網(wǎng)絡中，從發(fā)點到收點的包含節(jié)點的一條路由，必定包含一個頂點拆成的兩部分之間的那條弧。并且原圖的一對相鄰點及其間的邊被轉(zhuǎn)換成等效的由4個節(jié)點組成的“8”字形有向回路。因此，一個鏈路割集在切斷中到的所有有向路由方面，與在原始無向圖中去掉節(jié)點割集有相同作用，即中等于中。綜上，可得網(wǎng)絡節(jié)點連通度算法計算步驟如下。
第1步：對原網(wǎng)絡的任一節(jié)點對和，按上述規(guī)則構造新的有向網(wǎng)絡，并用標號法求中分離和的最小鏈路數(shù)，即中分離和的最小割點集點數(shù)。
第2步：對所有節(jié)點，計算，即得的邊連通度。
3 結論
本文討論了通信網(wǎng)絡可靠性的層次劃分與影響因素，針對性的分析了拓撲層可靠性的指標與測度，指出了“連通度”作為拓撲層可靠性基礎測度，以及其對其它測度設計的重要性。同時，詳細分析了節(jié)點連通度與邊連通度的計算思想與算法步驟。最后，通過一個相對簡單的算例演示了通過邊與節(jié)點連通度計算來評價某一通信網(wǎng)絡拓撲可靠性的主要流程。
無線移動通信網(wǎng)絡的拓撲結構會影響到網(wǎng)絡的性能，關系到網(wǎng)絡是否能高效、穩(wěn)定運行。發(fā)現(xiàn)網(wǎng)絡拓撲結構是對其進行高效管理的重要方面，它能揭示出網(wǎng)絡中的節(jié)點地理位置、與臨接點的關系、剩余電源、數(shù)據(jù)鏈路等信息。本文在較為理想的層次上通過仿真分析研究無線移動通信網(wǎng)絡拓撲結構的有效性。
【關鍵詞】無線移動通信網(wǎng) 拓撲結構 節(jié)點 有效性 鏈路
隨著網(wǎng)絡技術的發(fā)展和人們對網(wǎng)絡需求的增大，無線移動通信網(wǎng)絡也將不斷擴大規(guī)模，功能變得更加強大，而網(wǎng)絡結構也變得更加復雜，這個時候，網(wǎng)絡管理水平就關系到無線網(wǎng)安全穩(wěn)定運行水平。拓撲發(fā)現(xiàn)作為一項先進技術，在網(wǎng)絡管理中起重要作用。網(wǎng)絡的拓撲簡單來說是就是網(wǎng)絡節(jié)點的一種地圖，標記出所有節(jié)點的地理位置以及連通情況，分析網(wǎng)絡拓撲結構可以迅速發(fā)現(xiàn)網(wǎng)絡的數(shù)據(jù)傳輸路徑、網(wǎng)絡的承載能力等，網(wǎng)絡拓撲是監(jiān)視網(wǎng)絡運行的重要措施。
1 節(jié)點移動模型和鏈路有效性
1.1 節(jié)點移動模型
分析網(wǎng)絡節(jié)點的移動方式與性能分析有關，目前的節(jié)點移動模型多是從速度和時間角度來進行的，通過節(jié)點移動的速度和時間來判斷節(jié)點移動對網(wǎng)絡性能的影響。由于實際上的無線移動通信網(wǎng)絡中的節(jié)點移動是非常復雜的，為簡化流程，我們假定其處于較為理想的傳輸環(huán)境，采用簡單的二維隨機移動模型來進行節(jié)點的移動分析。
在一個無邊界限制的二維平面上，節(jié)點處于無序移動狀態(tài)，在一個基本單位時間里，節(jié)點的移動速度是相同的，在進入另一個基本時間單元時方改變速度。所以，節(jié)點在X軸和Y軸方向的方向移動中的速度和位移量都呈現(xiàn)出零均值正態(tài)分布，所以，節(jié)點在時間n的坐標為：
1.2 鏈路有效性
對于某覆蓋半徑為R的節(jié)點來說，其他節(jié)點與該節(jié)點存在鏈路都必須滿足r≤R的條件，否則的話就不存在鏈路關系。在一個無邊界限制的二維平面上，其節(jié)點的密度為ξ/，那么半徑為ρ的圓周中的節(jié)點密度為：fρ（ρ）=2πξρ。在進行節(jié)點的鏈路有效性測試時，就可以將該節(jié)點所覆蓋的范圍內(nèi)所有節(jié)點在某時刻鏈路中仍存在的平均節(jié)點數(shù)與總節(jié)點數(shù)的比值作為該節(jié)點的有效性測試結果。
2 仿真分析
無線移動通信網(wǎng)絡拓撲中的節(jié)點移動速度是有一定的限值的，我們最大的位移定義dm為：P{│Δx│>dm}=P{│Δy│>dm}≤ε，任何一個節(jié)點密度都存在σ=Kdm，本文將節(jié)點的密度定義為0.00135/，得出的K值為1/3。
2.1 鏈路有效性測試
為了確保仿真結果的準確性，進行多次仿真繪制仿真曲線，對覆蓋范圍的所有節(jié)點移動狀況進行10000次仿真，然后繪制出仿真曲線圖。
分析節(jié)點初始位置對鏈路有效性的影響，圖1中的三條仿真曲線分別是節(jié)點初始位置為4、8、10m時的仿真結果。從圖中可以明顯看出，隨著時間的推移，節(jié)點的鏈路有效性逐漸降低，當n=200時，三條仿真曲線的鏈路有效性相差不大，接下來的遞減速度也放緩。n在0-50范圍內(nèi)時，不同初始位置的節(jié)點鏈路有效性隨著時間的遞增而迅速降低。到n=100以后，不同初始位置的節(jié)點鏈路有效性隨著時間的推移遞減的速度放緩。這說明初始位置對鏈路有效性的影響在節(jié)點移動的剛開始一段時間，節(jié)點移動的時間長了之后，初始位置對鏈路有效性的影響逐漸變小。
2.2 拓撲結構有效性
假定場景的節(jié)點密度為1/，dm為4，改變覆蓋半徑R的大小進行仿真分析。如圖3所示為覆蓋半徑為4、8、16、32、64m時的仿真曲線圖，隨著節(jié)點移動時間的推移，拓撲結構的有效性也在降低。覆蓋半徑越大，拓撲結構的有效性越高，遞減的幅度也越小。覆蓋半徑為4、8m時，拓撲結構有效性在節(jié)點剛開始移動是呈現(xiàn)急劇降低現(xiàn)象，到n=50后，拓撲結構的有效性降低速度放緩。
3 結束語
無線移動通信網(wǎng)絡作為當前以及未來的主要網(wǎng)絡形式，其拓撲的有效性關系到網(wǎng)絡運行的穩(wěn)定和安全。拓撲圖中節(jié)點的無序移動會影響到網(wǎng)絡的有效性，本文以理想狀態(tài)下的網(wǎng)絡運行環(huán)境為背景建立了二維平面節(jié)點移動模型，經(jīng)過仿真分析，研究節(jié)點初始位置、節(jié)點覆蓋半徑大小、節(jié)點密度等對拓撲的有效性的影響，而現(xiàn)實環(huán)境中的網(wǎng)絡拓撲受到的外界干擾更多，其拓撲有效性還有待進一步研究。
摘要:該文通過分析通信網(wǎng)絡中的拓撲優(yōu)化問題,抽象出數(shù)學模型,并利用遺傳算法對該模型進行求解。最后通過實例驗證用遺傳算法求解該問題明顯優(yōu)于一些傳統(tǒng)的算法,文中所建立的數(shù)學模型和算法能夠正確地解決通信網(wǎng)絡拓撲優(yōu)化問題。
關鍵詞:遺傳算法;通信網(wǎng)絡;拓撲;優(yōu)化
隨著信息化的發(fā)展,通信網(wǎng)絡不斷擴充新功能,發(fā)展新業(yè)務。這必然導致網(wǎng)絡規(guī)模日益龐大,節(jié)點眾多,并且網(wǎng)絡拓撲的結構也越來越復雜。從而造成了數(shù)據(jù)信息的轉(zhuǎn)接次數(shù)增多,遲延增加,維護難度增大,這就給現(xiàn)代通信網(wǎng)絡的建設和管理提出了新的挑戰(zhàn)。
對通信網(wǎng)絡進行優(yōu)化能夠使其更加快速有效可靠地傳遞信息,避免和最大限度減少因網(wǎng)絡中斷或延遲帶來的損失。遺傳算法(GA)模擬自然進化過程,是一種具有并行特征的搜索算法,它能對解空間進行搜索,加快對解的搜索速度,便于推廣到多結點的網(wǎng)絡優(yōu)化設計中,是解決大規(guī)模網(wǎng)絡優(yōu)化問題的有效工具。
1 遺傳算法求解過程
遺傳算法(GA)的主要特點是直接對結構對象進行操作,具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力,自動獲取和指導優(yōu)化的搜索空間,自適應調(diào)整搜索方向,不需要確定的規(guī)則。
使用遺傳算法求解通信網(wǎng)絡的拓撲優(yōu)化一般采用如圖1的過程。
2 算法設計
2.1 編碼和初始化種群
對于一個n結點的網(wǎng)絡,其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個基因個體,每個基因個體都是此通信網(wǎng)絡的一種拓撲。
2.2 根據(jù)個體適應度進行選擇
求解網(wǎng)絡優(yōu)化的數(shù)學模型屬于求解目標函數(shù)最小值問題,適應度函數(shù)可設為
隨著進化代數(shù)的增加,個體適應度之間的差別越來越小,可以對適應度函數(shù)增加一個比例系數(shù)a將其放大,f’(x)=af(x),a>1。
2.3 算法終止條件
當種群滿足以下三個條件之一時算法終止并輸出最優(yōu)解。
1) 個體的最大適應度超過預先設定參數(shù)。
2) 個體的平均適應度超過預先設定參數(shù)。
3) 種群代數(shù)超過預先設定參數(shù)。
3 實驗及結果分析
某通信主干網(wǎng)絡節(jié)點數(shù)為9,經(jīng)過多次實驗后,選取POP=60,Pc=0.65,Pm=0.01, 并以最大代數(shù)max gen=3000做為程序的終止條件。其各節(jié)點間線路代價如表1所示。
經(jīng)過該算法可得到計算結果如圖3。
若采用枚舉法,則時間復雜度為O(2N),此算法時間復雜度為O(N2),所以在對通信網(wǎng)絡優(yōu)化的同時,大大降低了時間復雜度。
4 結論與總結
通信網(wǎng)絡的優(yōu)化是一個復雜且涉及范圍廣泛的課題,是通信網(wǎng)絡技術中不可缺少的部分。與遺傳算法相比,傳統(tǒng)算法比較復雜,局限性很大且計算時間較長。本文使用遺傳算法較好地解決了通信網(wǎng)絡優(yōu)化問題。本文提出的算法對小規(guī)模通信網(wǎng)絡的拓撲優(yōu)化問題能夠較好的求解,對大規(guī)模網(wǎng)絡拓撲進行優(yōu)化還存在不足。改進方法可以在遺傳算法中融合其它優(yōu)化算法,構成一種混合遺傳算法。本文中對遺傳算法在網(wǎng)絡優(yōu)化中的研究只進行了初步的探討,要將這種方法完善還需要做進一步探討和研究。
