序言：寫作是分享個人見解和探索未知領(lǐng)域的橋梁，我們?yōu)槟x了1篇的通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析研究樣本，期待這些樣本能夠為您提供豐富的參考和啟發(fā)，請盡情閱讀。

通信網(wǎng)絡(luò)拓?fù)?/a>結(jié)構(gòu)分析研究:通信網(wǎng)絡(luò)拓?fù)淇煽啃詫哟闻c測度研究

摘 要：梳理討論了目前通信網(wǎng)絡(luò)可靠性研究之間的層次關(guān)系，討論了拓?fù)淇煽啃运幍牡匚弧⑷蝿?wù)、指標(biāo)等。其次，分析了拓?fù)淇煽啃缘姆歉怕蕼y度，指出了連通度的核心作用。再次，研究了基于邊連通度與節(jié)點(diǎn)連通度進(jìn)行可靠性評價的思想與算法。最后，通過一個算例展示了通信網(wǎng)絡(luò)拓?fù)淇煽啃栽u價的具體過程。

關(guān)鍵詞：通信網(wǎng)路 可靠性 層次 測度

隨著通信、信息、網(wǎng)絡(luò)技術(shù)的高速發(fā)展與廣泛應(yīng)用，人們對通信網(wǎng)絡(luò)的依賴愈加明顯，隨之而來的可靠性問題日益成為用戶關(guān)注的焦點(diǎn)領(lǐng)域。現(xiàn)代通信網(wǎng)絡(luò)是一個復(fù)雜系統(tǒng)，融合了多學(xué)科領(lǐng)域，因此對其可靠性的研究是一項系統(tǒng)工程。

從目前的公開文獻(xiàn)來看，通信網(wǎng)絡(luò)可靠性研究分布于網(wǎng)絡(luò)應(yīng)用的各個層次與領(lǐng)域，一般可對應(yīng)于OIS（Open System Interconnect）系統(tǒng)模型的劃分。同時，通信網(wǎng)絡(luò)的復(fù)雜性、動態(tài)性、多態(tài)性等屬性為可靠性評估與優(yōu)化提出了新的挑戰(zhàn)，導(dǎo)致了研究的視角與側(cè)重點(diǎn)也不盡相同。拓?fù)浣Y(jié)構(gòu)是通信網(wǎng)絡(luò)的核心特征，其依據(jù)拓?fù)鋪斫M織網(wǎng)絡(luò)形態(tài)，進(jìn)而體現(xiàn)通信網(wǎng)絡(luò)系統(tǒng)的整體性。因此，對通信網(wǎng)絡(luò)拓?fù)淇煽啃缘难芯刻幱谡麄€通信網(wǎng)絡(luò)可靠性研究的中心地位。

1 通信網(wǎng)絡(luò)可靠性研究的層次體系

1.1 拓?fù)淇煽啃蕴幱诤诵牡匚?

如引言中所述，拓?fù)淇煽啃圆⒉荒芡耆碚髡麄€通信網(wǎng)絡(luò)的可靠性，其研究對象只關(guān)注于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，忽略了網(wǎng)絡(luò)通信設(shè)備、路由策略、承載業(yè)務(wù)、管理效率等因素所帶來的可靠性變化。拓?fù)鋵痈哂谠O(shè)備層，同時是路由層、業(yè)務(wù)層等高層可靠性的基礎(chǔ)，在整個通信網(wǎng)絡(luò)可靠性中處于承上啟下的中間環(huán)節(jié)，其影響可見一斑。

通信網(wǎng)絡(luò)可靠性可分層討論，每層均應(yīng)設(shè)計相應(yīng)的指標(biāo)與測度方法，以完成對通信網(wǎng)絡(luò)可靠性的定量描述。因此，通信網(wǎng)絡(luò)可靠性應(yīng)具備一個同向、協(xié)調(diào)、完備的指標(biāo)體系。在對目前文獻(xiàn)梳理的基礎(chǔ)之上，可得可靠性指標(biāo)體系。同時，各文獻(xiàn)對可靠性的理解與劃分具有相互重疊性，而且關(guān)于同一類指標(biāo)的描述也不盡相同，新的指標(biāo)也不斷被提出。

1.2 拓?fù)淇煽啃灾笜?biāo)分析

在網(wǎng)絡(luò)拓?fù)淇煽啃缘闹笜?biāo)描述上是想通的，即在抗毀性與生存性上具有廣泛共識。同時可見，連通度是兩者的指標(biāo)與測度設(shè)計的基礎(chǔ)因素。

（1）網(wǎng)絡(luò)拓?fù)淇箽?。主要用于刻畫在確定的網(wǎng)絡(luò)組織結(jié)構(gòu)（即網(wǎng)絡(luò)拓?fù)洌?、預(yù)定的破壞（攻擊）方案下，通信網(wǎng)絡(luò)依然能夠保持全網(wǎng)或部分連通（物理可達(dá)）的能力。在對實(shí)際網(wǎng)絡(luò)進(jìn)行拓?fù)涑橄笾?，抗毀性指要破壞（中斷）部分網(wǎng)絡(luò)節(jié)點(diǎn)連接需要移除（破壞）的最少網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路（邊）的數(shù)目，從而表征出破壞整個或部分通信網(wǎng)絡(luò)的困難程度?？梢?，抗毀性完全由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)所決定，是可靠性的一個確定型指標(biāo)。

（2）網(wǎng)絡(luò)拓?fù)渖嫘?。生存性最顯著的變化是引入了網(wǎng)絡(luò)部件的失效（故障）概率，用于刻畫在隨機(jī)故障或蓄意破壞之下，保持通信網(wǎng)絡(luò)整體或部分連通的概率。其建立在圖論與概率論基礎(chǔ)之上的可靠性分析，不僅受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響，同時還依附于網(wǎng)絡(luò)部件（設(shè)備）的故障概率與模式、網(wǎng)絡(luò)維修與管理等因素，因此網(wǎng)絡(luò)拓?fù)渖嫘允菑V義的拓?fù)鋵涌煽啃浴?

2 基于連通的通信網(wǎng)絡(luò)拓?fù)淇煽啃詼y度

通信網(wǎng)絡(luò)拓?fù)淇煽啃詥栴}可抽象為圖的可靠性問題，用圖G（V，E）來描述拓?fù)浣Y(jié)構(gòu)。其中，V表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，例如用戶終端、服務(wù)端、路由服務(wù)器等；E表示連接網(wǎng)絡(luò)中節(jié)點(diǎn)的邊（鏈路）集合。同時，本節(jié)主要討論拓?fù)淇煽啃缘姆歉怕剩o態(tài)）測度，即不考慮上層業(yè)務(wù)或下層設(shè)備影響，將問題視角完全限定在拓?fù)鋵用妗?

目前，關(guān)于拓?fù)淇煽啃缘撵o態(tài)測度研究很多，可謂仁者見仁，測度設(shè)計的側(cè)重點(diǎn)各不相同。例如：連通度（vertex connectivity）、堅韌度（toughness）、完整度（integrity）、粘連度（tenacity）、離散數(shù)（scattering number）、膨脹系數(shù)（expansion coefficient）等。其中，連通度是拓?fù)涞幕A(chǔ)指標(biāo)，后續(xù)的測度均建立在對連通性的充分考慮的基礎(chǔ)之上。因此，本節(jié)以連通度為重點(diǎn)展開討論。

2.1 邊連通度與節(jié)點(diǎn)連通度的定義

（1）邊連通度。

記為，其大小等于使網(wǎng)絡(luò)成為不連通圖所需去掉鏈路（邊）的最少條數(shù)。它反映網(wǎng)絡(luò)節(jié)點(diǎn)間的內(nèi)聚程度，是網(wǎng)絡(luò)可靠性的一個基本度量指標(biāo)。例如：通過分析可知，所示的網(wǎng)絡(luò)分割至少需要移除3條邊，即邊連通度。

（2）節(jié)點(diǎn)連通度。

也成為點(diǎn)連通度，記為，其大小等于使網(wǎng)絡(luò)成為不連通圖所需去掉的節(jié)點(diǎn)的最少個數(shù)。同理，網(wǎng)絡(luò)的連通度。從某種意義上講，點(diǎn)連通度是比邊連通度更重要的網(wǎng)絡(luò)可靠性度量指標(biāo)，這是因為在網(wǎng)絡(luò)中去掉某個節(jié)點(diǎn)就意味著與之關(guān)聯(lián)的所有鏈路將失去意義。

2.2 邊連通度與節(jié)點(diǎn)連通度的算法

（1）算法的基本思想。

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

2）網(wǎng)絡(luò)邊連通度計算步驟。

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

第1步：對給定網(wǎng)絡(luò)，任選一對節(jié)點(diǎn)和，按下面的步驟求分離和的最小鏈路數(shù)：

①首先將轉(zhuǎn)換成有向圖。方法是：將鏈路集中以為端點(diǎn)的鏈路轉(zhuǎn)換成中以為起點(diǎn)的到相應(yīng)節(jié)點(diǎn)的有向鏈路，將中以為端點(diǎn)的鏈路轉(zhuǎn)換成中從相應(yīng)節(jié)點(diǎn)到節(jié)點(diǎn)的有向鏈路，又將中其他鏈路轉(zhuǎn)換成中2條有向鏈路和。

②用標(biāo)號算法，求中分離與的最小鏈路數(shù)。

第2步：對所有節(jié)點(diǎn)對，，重復(fù)上述步驟計算，最后計算：，即網(wǎng)絡(luò)的邊連通度。需要注意的是：由于，對于含有個節(jié)點(diǎn)的圖，第2步中需要計算的共有個。

3）網(wǎng)絡(luò)節(jié)點(diǎn)連通度計算步驟。

算法的思路是：將割點(diǎn)問題轉(zhuǎn)換成割邊問題，從而使求網(wǎng)絡(luò)節(jié)點(diǎn)連通度的問題轉(zhuǎn)換成求網(wǎng)絡(luò)的邊連通度問題。轉(zhuǎn)換的方法是：在網(wǎng)絡(luò)中任選一對節(jié)點(diǎn)和，首先，類似于邊連通度算法一樣，將轉(zhuǎn)換成有向網(wǎng)絡(luò)，然后，再將構(gòu)造另一個有向圖，構(gòu)圖規(guī)則是：將中除和外的每個節(jié)點(diǎn)拆成2個新的中的節(jié)點(diǎn)和，并用中的有向鏈路將它們連接起來。將中每一鏈路換成中的鏈路，并把標(biāo)為，標(biāo)為。

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

第1步：對原網(wǎng)絡(luò)的任一節(jié)點(diǎn)對和，按上述規(guī)則構(gòu)造新的有向網(wǎng)絡(luò)，并用標(biāo)號法求中分離和的最小鏈路數(shù)，即中分離和的最小割點(diǎn)集點(diǎn)數(shù)。

第2步：對所有節(jié)點(diǎn)，計算，即得的邊連通度。

3 結(jié)論

本文討論了通信網(wǎng)絡(luò)可靠性的層次劃分與影響因素，針對性的分析了拓?fù)鋵涌煽啃缘闹笜?biāo)與測度，指出了“連通度”作為拓?fù)鋵涌煽啃曰A(chǔ)測度，以及其對其它測度設(shè)計的重要性。同時，詳細(xì)分析了節(jié)點(diǎn)連通度與邊連通度的計算思想與算法步驟。最后，通過一個相對簡單的算例演示了通過邊與節(jié)點(diǎn)連通度計算來評價某一通信網(wǎng)絡(luò)拓?fù)淇煽啃缘闹饕鞒獭?

通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析研究:關(guān)于無線移動通信網(wǎng)絡(luò)拓?fù)溆行缘难芯砍跆?

無線移動通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會影響到網(wǎng)絡(luò)的性能，關(guān)系到網(wǎng)絡(luò)是否能高效、穩(wěn)定運(yùn)行。發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是對其進(jìn)行高效管理的重要方面，它能揭示出網(wǎng)絡(luò)中的節(jié)點(diǎn)地理位置、與臨接點(diǎn)的關(guān)系、剩余電源、數(shù)據(jù)鏈路等信息。本文在較為理想的層次上通過仿真分析研究無線移動通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的有效性。

【關(guān)鍵詞】無線移動通信網(wǎng) 拓?fù)浣Y(jié)構(gòu) 節(jié)點(diǎn) 有效性 鏈路

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和人們對網(wǎng)絡(luò)需求的增大，無線移動通信網(wǎng)絡(luò)也將不斷擴(kuò)大規(guī)模，功能變得更加強(qiáng)大，而網(wǎng)絡(luò)結(jié)構(gòu)也變得更加復(fù)雜，這個時候，網(wǎng)絡(luò)管理水平就關(guān)系到無線網(wǎng)安全穩(wěn)定運(yùn)行水平。拓?fù)浒l(fā)現(xiàn)作為一項先進(jìn)技術(shù)，在網(wǎng)絡(luò)管理中起重要作用。網(wǎng)絡(luò)的拓?fù)浜唵蝸碚f是就是網(wǎng)絡(luò)節(jié)點(diǎn)的一種地圖，標(biāo)記出所有節(jié)點(diǎn)的地理位置以及連通情況，分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以迅速發(fā)現(xiàn)網(wǎng)絡(luò)的數(shù)據(jù)傳輸路徑、網(wǎng)絡(luò)的承載能力等，網(wǎng)絡(luò)拓?fù)涫潜O(jiān)視網(wǎng)絡(luò)運(yùn)行的重要措施。

1 節(jié)點(diǎn)移動模型和鏈路有效性

1.1 節(jié)點(diǎn)移動模型

分析網(wǎng)絡(luò)節(jié)點(diǎn)的移動方式與性能分析有關(guān)，目前的節(jié)點(diǎn)移動模型多是從速度和時間角度來進(jìn)行的，通過節(jié)點(diǎn)移動的速度和時間來判斷節(jié)點(diǎn)移動對網(wǎng)絡(luò)性能的影響。由于實(shí)際上的無線移動通信網(wǎng)絡(luò)中的節(jié)點(diǎn)移動是非常復(fù)雜的，為簡化流程，我們假定其處于較為理想的傳輸環(huán)境，采用簡單的二維隨機(jī)移動模型來進(jìn)行節(jié)點(diǎn)的移動分析。

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

1.2 鏈路有效性

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

2 仿真分析

無線移動通信網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)移動速度是有一定的限值的，我們最大的位移定義dm為：P{│Δx│>dm}=P{│Δy│>dm}≤ε，任何一個節(jié)點(diǎn)密度都存在σ=Kdm，本文將節(jié)點(diǎn)的密度定義為0.00135/，得出的K值為1/3。

2.1 鏈路有效性測試

為了確保仿真結(jié)果的準(zhǔn)確性，進(jìn)行多次仿真繪制仿真曲線，對覆蓋范圍的所有節(jié)點(diǎn)移動狀況進(jìn)行10000次仿真，然后繪制出仿真曲線圖。

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

2.2 拓?fù)浣Y(jié)構(gòu)有效性

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

3 結(jié)束語

無線移動通信網(wǎng)絡(luò)作為當(dāng)前以及未來的主要網(wǎng)絡(luò)形式，其拓?fù)涞挠行躁P(guān)系到網(wǎng)絡(luò)運(yùn)行的穩(wěn)定和安全。拓?fù)鋱D中節(jié)點(diǎn)的無序移動會影響到網(wǎng)絡(luò)的有效性，本文以理想狀態(tài)下的網(wǎng)絡(luò)運(yùn)行環(huán)境為背景建立了二維平面節(jié)點(diǎn)移動模型，經(jīng)過仿真分析，研究節(jié)點(diǎn)初始位置、節(jié)點(diǎn)覆蓋半徑大小、節(jié)點(diǎn)密度等對拓?fù)涞挠行缘挠绊?，而現(xiàn)實(shí)環(huán)境中的網(wǎng)絡(luò)拓?fù)涫艿降耐饨绺蓴_更多，其拓?fù)溆行赃€有待進(jìn)一步研究。

通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析研究:基于遺傳算法的通信網(wǎng)絡(luò)拓?fù)鋬?yōu)化研究

摘要:該文通過分析通信網(wǎng)絡(luò)中的拓?fù)鋬?yōu)化問題,抽象出數(shù)學(xué)模型,并利用遺傳算法對該模型進(jìn)行求解。最后通過實(shí)例驗證用遺傳算法求解該問題明顯優(yōu)于一些傳統(tǒng)的算法,文中所建立的數(shù)學(xué)模型和算法能夠正確地解決通信網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題。

關(guān)鍵詞:遺傳算法;通信網(wǎng)絡(luò);拓?fù)?優(yōu)化

隨著信息化的發(fā)展,通信網(wǎng)絡(luò)不斷擴(kuò)充新功能,發(fā)展新業(yè)務(wù)。這必然導(dǎo)致網(wǎng)絡(luò)規(guī)模日益龐大,節(jié)點(diǎn)眾多,并且網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)也越來越復(fù)雜。從而造成了數(shù)據(jù)信息的轉(zhuǎn)接次數(shù)增多,遲延增加,維護(hù)難度增大,這就給現(xiàn)代通信網(wǎng)絡(luò)的建設(shè)和管理提出了新的挑戰(zhàn)。

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

1 遺傳算法求解過程

遺傳算法(GA)的主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作,具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力,自動獲取和指導(dǎo)優(yōu)化的搜索空間,自適應(yīng)調(diào)整搜索方向,不需要確定的規(guī)則。

使用遺傳算法求解通信網(wǎng)絡(luò)的拓?fù)鋬?yōu)化一般采用如圖1的過程。

2 算法設(shè)計

2.1 編碼和初始化種群

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

圖2 G的鄰接矩陣T

在上述編碼方式中,則基因型可設(shè)為A[1,…,n(n-1)/2],由此可以生成W個基因個體,每個基因個體都是此通信網(wǎng)絡(luò)的一種拓?fù)洹?

2.2 根據(jù)個體適應(yīng)度進(jìn)行選擇

求解網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)模型屬于求解目標(biāo)函數(shù)最小值問題,適應(yīng)度函數(shù)可設(shè)為

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

2.3 算法終止條件

當(dāng)種群滿足以下三個條件之一時算法終止并輸出最優(yōu)解。

1) 個體的最大適應(yīng)度超過預(yù)先設(shè)定參數(shù)。

2) 個體的平均適應(yīng)度超過預(yù)先設(shè)定參數(shù)。

3) 種群代數(shù)超過預(yù)先設(shè)定參數(shù)。

3 實(shí)驗及結(jié)果分析

某通信主干網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為9,經(jīng)過多次實(shí)驗后,選取POP=60,Pc=0.65,Pm=0.01, 并以最大代數(shù)max gen=3000做為程序的終止條件。其各節(jié)點(diǎn)間線路代價如表1所示。

經(jīng)過該算法可得到計算結(jié)果如圖3。

若采用枚舉法,則時間復(fù)雜度為O(2N),此算法時間復(fù)雜度為O(N2),所以在對通信網(wǎng)絡(luò)優(yōu)化的同時,大大降低了時間復(fù)雜度。

4 結(jié)論與總結(jié)

通信網(wǎng)絡(luò)的優(yōu)化是一個復(fù)雜且涉及范圍廣泛的課題,是通信網(wǎng)絡(luò)技術(shù)中不可缺少的部分。與遺傳算法相比,傳統(tǒng)算法比較復(fù)雜,局限性很大且計算時間較長。本文使用遺傳算法較好地解決了通信網(wǎng)絡(luò)優(yōu)化問題。本文提出的算法對小規(guī)模通信網(wǎng)絡(luò)的拓?fù)鋬?yōu)化問題能夠較好的求解,對大規(guī)模網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化還存在不足。改進(jìn)方法可以在遺傳算法中融合其它優(yōu)化算法,構(gòu)成一種混合遺傳算法。本文中對遺傳算法在網(wǎng)絡(luò)優(yōu)化中的研究只進(jìn)行了初步的探討,要將這種方法完善還需要做進(jìn)一步探討和研究。