時(shí)間：2022-07-26 04:56:30
引言：易發(fā)表網(wǎng)憑借豐富的文秘實(shí)踐，為您精心挑選了一篇通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析研究范例。如需獲取更多原創(chuàng)內(nèi)容，可隨時(shí)聯(lián)系我們的客服老師。
摘 要：梳理討論了目前通信網(wǎng)絡(luò)可靠性研究之間的層次關(guān)系，討論了拓?fù)淇煽啃运幍牡匚弧⑷蝿?wù)、指標(biāo)等。其次，分析了拓?fù)淇煽啃缘姆歉怕蕼y(cè)度，指出了連通度的核心作用。再次，研究了基于邊連通度與節(jié)點(diǎn)連通度進(jìn)行可靠性評(píng)價(jià)的思想與算法。最后，通過一個(gè)算例展示了通信網(wǎng)絡(luò)拓?fù)淇煽啃栽u(píng)價(jià)的具體過程。
關(guān)鍵詞：通信網(wǎng)路 可靠性 層次 測(cè)度
隨著通信、信息、網(wǎng)絡(luò)技術(shù)的高速發(fā)展與廣泛應(yīng)用，人們對(duì)通信網(wǎng)絡(luò)的依賴愈加明顯，隨之而來的可靠性問題日益成為用戶關(guān)注的焦點(diǎn)領(lǐng)域。現(xiàn)代通信網(wǎng)絡(luò)是一個(gè)復(fù)雜系統(tǒng)，融合了多學(xué)科領(lǐng)域，因此對(duì)其可靠性的研究是一項(xiàng)系統(tǒng)工程。
從目前的公開文獻(xiàn)來看，通信網(wǎng)絡(luò)可靠性研究分布于網(wǎng)絡(luò)應(yīng)用的各個(gè)層次與領(lǐng)域，一般可對(duì)應(yīng)于OIS（Open System Interconnect）系統(tǒng)模型的劃分。同時(shí)，通信網(wǎng)絡(luò)的復(fù)雜性、動(dòng)態(tài)性、多態(tài)性等屬性為可靠性評(píng)估與優(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)的整體性。因此，對(duì)通信網(wǎng)絡(luò)拓?fù)淇煽啃缘难芯刻幱谡麄€(gè)通信網(wǎng)絡(luò)可靠性研究的中心地位。
1 通信網(wǎng)絡(luò)可靠性研究的層次體系
1.1 拓?fù)淇煽啃蕴幱诤诵牡匚?
如引言中所述，拓?fù)淇煽啃圆⒉荒芡耆碚髡麄€(gè)通信網(wǎng)絡(luò)的可靠性，其研究對(duì)象只關(guān)注于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，忽略了網(wǎng)絡(luò)通信設(shè)備、路由策略、承載業(yè)務(wù)、管理效率等因素所帶來的可靠性變化。拓?fù)鋵痈哂谠O(shè)備層，同時(shí)是路由層、業(yè)務(wù)層等高層可靠性的基礎(chǔ)，在整個(gè)通信網(wǎng)絡(luò)可靠性中處于承上啟下的中間環(huán)節(jié)，其影響可見一斑。
通信網(wǎng)絡(luò)可靠性可分層討論，每層均應(yīng)設(shè)計(jì)相應(yīng)的指標(biāo)與測(cè)度方法，以完成對(duì)通信網(wǎng)絡(luò)可靠性的定量描述。因此，通信網(wǎng)絡(luò)可靠性應(yīng)具備一個(gè)同向、協(xié)調(diào)、完備的指標(biāo)體系。在對(duì)目前文獻(xiàn)梳理的基礎(chǔ)之上，可得可靠性指標(biāo)體系。同時(shí)，各文獻(xiàn)對(duì)可靠性的理解與劃分具有相互重疊性，而且關(guān)于同一類指標(biāo)的描述也不盡相同，新的指標(biāo)也不斷被提出。
1.2 拓?fù)淇煽啃灾笜?biāo)分析
在網(wǎng)絡(luò)拓?fù)淇煽啃缘闹笜?biāo)描述上是想通的，即在抗毀性與生存性上具有廣泛共識(shí)。同時(shí)可見，連通度是兩者的指標(biāo)與測(cè)度設(shè)計(jì)的基礎(chǔ)因素。
（1）網(wǎng)絡(luò)拓?fù)淇箽浴Ｖ饕糜诳坍嬙诖_定的網(wǎng)絡(luò)組織結(jié)構(gòu)（即網(wǎng)絡(luò)拓?fù)洌㈩A(yù)定的破壞（攻擊）方案下，通信網(wǎng)絡(luò)依然能夠保持全網(wǎng)或部分連通（物理可達(dá)）的能力。在對(duì)實(shí)際網(wǎng)絡(luò)進(jìn)行拓?fù)涑橄笾螅箽灾敢茐模ㄖ袛啵┎糠志W(wǎng)絡(luò)節(jié)點(diǎn)連接需要移除（破壞）的最少網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路（邊）的數(shù)目，從而表征出破壞整個(gè)或部分通信網(wǎng)絡(luò)的困難程度。可見，抗毀性完全由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)所決定，是可靠性的一個(gè)確定型指標(biāo)。
（2）網(wǎng)絡(luò)拓?fù)渖嫘浴Ｉ嫘宰铒@著的變化是引入了網(wǎng)絡(luò)部件的失效（故障）概率，用于刻畫在隨機(jī)故障或蓄意破壞之下，保持通信網(wǎng)絡(luò)整體或部分連通的概率。其建立在圖論與概率論基礎(chǔ)之上的可靠性分析，不僅受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響，同時(shí)還依附于網(wǎng)絡(luò)部件（設(shè)備）的故障概率與模式、網(wǎng)絡(luò)維修與管理等因素，因此網(wǎng)絡(luò)拓?fù)渖嫘允菑V義的拓?fù)鋵涌煽啃浴?
2 基于連通的通信網(wǎng)絡(luò)拓?fù)淇煽啃詼y(cè)度
通信網(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)的邊（鏈路）集合。同時(shí)，本節(jié)主要討論拓?fù)淇煽啃缘姆歉怕剩o態(tài)）測(cè)度，即不考慮上層業(yè)務(wù)或下層設(shè)備影響，將問題視角完全限定在拓?fù)鋵用妗?
目前，關(guān)于拓?fù)淇煽啃缘撵o態(tài)測(cè)度研究很多，可謂仁者見仁，測(cè)度設(shè)計(jì)的側(cè)重點(diǎn)各不相同。例如：連通度（vertex connectivity）、堅(jiān)韌度（toughness）、完整度（integrity）、粘連度（tenacity）、離散數(shù)（scattering number）、膨脹系數(shù)（expansion coefficient）等。其中，連通度是拓?fù)涞幕A(chǔ)指標(biāo)，后續(xù)的測(cè)度均建立在對(duì)連通性的充分考慮的基礎(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ò)可靠性的一個(gè)基本度量指標(biāo)。例如：通過分析可知，所示的網(wǎng)絡(luò)分割至少需要移除3條邊，即邊連通度。
（2）節(jié)點(diǎn)連通度。
也成為點(diǎn)連通度，記為，其大小等于使網(wǎng)絡(luò)成為不連通圖所需去掉的節(jié)點(diǎn)的最少個(gè)數(shù)。同理，網(wǎng)絡(luò)的連通度。從某種意義上講，點(diǎn)連通度是比邊連通度更重要的網(wǎng)絡(luò)可靠性度量指標(biāo)，這是因?yàn)樵诰W(wǎng)絡(luò)中去掉某個(gè)節(jié)點(diǎn)就意味著與之關(guān)聯(lián)的所有鏈路將失去意義。
2.2 邊連通度與節(jié)點(diǎn)連通度的算法
（1）算法的基本思想。
通常，要求給定網(wǎng)絡(luò)的邊連通度，需要首先確定任意不同兩點(diǎn)的鏈路割集。設(shè)和是的兩個(gè)不同節(jié)點(diǎn)，所謂的一個(gè)鏈路割集是指這樣的鏈路集合：若去掉其中所有鏈路，網(wǎng)絡(luò)將被分割成兩個(gè)分支，一個(gè)包含節(jié)點(diǎn)；另一個(gè)包含節(jié)點(diǎn)。假設(shè)是中所有鏈路割集中鏈路的最小數(shù)，則就是切斷和之間所有路由所需從中刪去的最小鏈路數(shù)，故網(wǎng)絡(luò)的邊連通度可按（1）式計(jì)算：
2）網(wǎng)絡(luò)邊連通度計(jì)算步驟。
由前所述，計(jì)算網(wǎng)絡(luò)邊連通度的算法思路是：先按標(biāo)號(hào)算法求分離任兩點(diǎn)的最小鏈路數(shù)，然后，再求所有這些數(shù)的最小數(shù)即可。但是，上述求的算法是針對(duì)有向圖給出的，而網(wǎng)絡(luò)邊連通度是針對(duì)無向圖的，因此，算法需首先將原無向網(wǎng)絡(luò)轉(zhuǎn)換成等效的有向網(wǎng)絡(luò)。具體計(jì)算步驟如下：
第1步：對(duì)給定網(wǎng)絡(luò)，任選一對(duì)節(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)號(hào)算法，求中分離與的最小鏈路數(shù)。
第2步：對(duì)所有節(jié)點(diǎn)對(duì)，，重復(fù)上述步驟計(jì)算，最后計(jì)算：，即網(wǎng)絡(luò)的邊連通度。需要注意的是：由于，對(duì)于含有個(gè)節(jié)點(diǎn)的圖，第2步中需要計(jì)算的共有個(gè)。
3）網(wǎng)絡(luò)節(jié)點(diǎn)連通度計(jì)算步驟。
算法的思路是：將割點(diǎn)問題轉(zhuǎn)換成割邊問題，從而使求網(wǎng)絡(luò)節(jié)點(diǎn)連通度的問題轉(zhuǎn)換成求網(wǎng)絡(luò)的邊連通度問題。轉(zhuǎn)換的方法是：在網(wǎng)絡(luò)中任選一對(duì)節(jié)點(diǎn)和，首先，類似于邊連通度算法一樣，將轉(zhuǎn)換成有向網(wǎng)絡(luò)，然后，再將構(gòu)造另一個(gè)有向圖，構(gòu)圖規(guī)則是：將中除和外的每個(gè)節(jié)點(diǎn)拆成2個(gè)新的中的節(jié)點(diǎn)和，并用中的有向鏈路將它們連接起來。將中每一鏈路換成中的鏈路，并把標(biāo)為，標(biāo)為。
由構(gòu)圖規(guī)則可知，在新的網(wǎng)絡(luò)中，從發(fā)點(diǎn)到收點(diǎn)的包含節(jié)點(diǎn)的一條路由，必定包含一個(gè)頂點(diǎn)拆成的兩部分之間的那條弧。并且原圖的一對(duì)相鄰點(diǎn)及其間的邊被轉(zhuǎn)換成等效的由4個(gè)節(jié)點(diǎn)組成的“8”字形有向回路。因此，一個(gè)鏈路割集在切斷中到的所有有向路由方面，與在原始無向圖中去掉節(jié)點(diǎn)割集有相同作用，即中等于中。綜上，可得網(wǎng)絡(luò)節(jié)點(diǎn)連通度算法計(jì)算步驟如下。
第1步：對(duì)原網(wǎng)絡(luò)的任一節(jié)點(diǎn)對(duì)和，按上述規(guī)則構(gòu)造新的有向網(wǎng)絡(luò)，并用標(biāo)號(hào)法求中分離和的最小鏈路數(shù)，即中分離和的最小割點(diǎn)集點(diǎn)數(shù)。
第2步：對(duì)所有節(jié)點(diǎn)，計(jì)算，即得的邊連通度。
3 結(jié)論
本文討論了通信網(wǎng)絡(luò)可靠性的層次劃分與影響因素，針對(duì)性的分析了拓?fù)鋵涌煽啃缘闹笜?biāo)與測(cè)度，指出了“連通度”作為拓?fù)鋵涌煽啃曰A(chǔ)測(cè)度，以及其對(duì)其它測(cè)度設(shè)計(jì)的重要性。同時(shí)，詳細(xì)分析了節(jié)點(diǎn)連通度與邊連通度的計(jì)算思想與算法步驟。最后，通過一個(gè)相對(duì)簡單的算例演示了通過邊與節(jié)點(diǎn)連通度計(jì)算來評(píng)價(jià)某一通信網(wǎng)絡(luò)拓?fù)淇煽啃缘闹饕鞒獭?
無線移動(dòng)通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會(huì)影響到網(wǎng)絡(luò)的性能，關(guān)系到網(wǎng)絡(luò)是否能高效、穩(wěn)定運(yùn)行。發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是對(duì)其進(jìn)行高效管理的重要方面，它能揭示出網(wǎng)絡(luò)中的節(jié)點(diǎn)地理位置、與臨接點(diǎn)的關(guān)系、剩余電源、數(shù)據(jù)鏈路等信息。本文在較為理想的層次上通過仿真分析研究無線移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的有效性。
【關(guān)鍵詞】無線移動(dòng)通信網(wǎng) 拓?fù)浣Y(jié)構(gòu) 節(jié)點(diǎn) 有效性 鏈路
隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和人們對(duì)網(wǎng)絡(luò)需求的增大，無線移動(dòng)通信網(wǎng)絡(luò)也將不斷擴(kuò)大規(guī)模，功能變得更加強(qiáng)大，而網(wǎng)絡(luò)結(jié)構(gòu)也變得更加復(fù)雜，這個(gè)時(shí)候，網(wǎng)絡(luò)管理水平就關(guān)系到無線網(wǎng)安全穩(wěn)定運(yùn)行水平。拓?fù)浒l(fā)現(xiàn)作為一項(xiàng)先進(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)移動(dòng)模型和鏈路有效性
1.1 節(jié)點(diǎn)移動(dòng)模型
分析網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)方式與性能分析有關(guān)，目前的節(jié)點(diǎn)移動(dòng)模型多是從速度和時(shí)間角度來進(jìn)行的，通過節(jié)點(diǎn)移動(dòng)的速度和時(shí)間來判斷節(jié)點(diǎn)移動(dòng)對(duì)網(wǎng)絡(luò)性能的影響。由于實(shí)際上的無線移動(dòng)通信網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)是非常復(fù)雜的，為簡化流程，我們假定其處于較為理想的傳輸環(huán)境，采用簡單的二維隨機(jī)移動(dòng)模型來進(jìn)行節(jié)點(diǎn)的移動(dòng)分析。
在一個(gè)無邊界限制的二維平面上，節(jié)點(diǎn)處于無序移動(dòng)狀態(tài)，在一個(gè)基本單位時(shí)間里，節(jié)點(diǎn)的移動(dòng)速度是相同的，在進(jìn)入另一個(gè)基本時(shí)間單元時(shí)方改變速度。所以，節(jié)點(diǎn)在X軸和Y軸方向的方向移動(dòng)中的速度和位移量都呈現(xiàn)出零均值正態(tài)分布，所以，節(jié)點(diǎn)在時(shí)間n的坐標(biāo)為：
1.2 鏈路有效性
對(duì)于某覆蓋半徑為R的節(jié)點(diǎn)來說，其他節(jié)點(diǎn)與該節(jié)點(diǎn)存在鏈路都必須滿足r≤R的條件，否則的話就不存在鏈路關(guān)系。在一個(gè)無邊界限制的二維平面上，其節(jié)點(diǎn)的密度為ξ/，那么半徑為ρ的圓周中的節(jié)點(diǎn)密度為：fρ（ρ）=2πξρ。在進(jìn)行節(jié)點(diǎn)的鏈路有效性測(cè)試時(shí)，就可以將該節(jié)點(diǎn)所覆蓋的范圍內(nèi)所有節(jié)點(diǎn)在某時(shí)刻鏈路中仍存在的平均節(jié)點(diǎn)數(shù)與總節(jié)點(diǎn)數(shù)的比值作為該節(jié)點(diǎn)的有效性測(cè)試結(jié)果。
2 仿真分析
無線移動(dòng)通信網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)移動(dòng)速度是有一定的限值的，我們最大的位移定義dm為：P{│Δx│>dm}=P{│Δy│>dm}≤ε，任何一個(gè)節(jié)點(diǎn)密度都存在σ=Kdm，本文將節(jié)點(diǎn)的密度定義為0.00135/，得出的K值為1/3。
2.1 鏈路有效性測(cè)試
為了確保仿真結(jié)果的準(zhǔn)確性，進(jìn)行多次仿真繪制仿真曲線，對(duì)覆蓋范圍的所有節(jié)點(diǎn)移動(dòng)狀況進(jìn)行10000次仿真，然后繪制出仿真曲線圖。
分析節(jié)點(diǎn)初始位置對(duì)鏈路有效性的影響，圖1中的三條仿真曲線分別是節(jié)點(diǎn)初始位置為4、8、10m時(shí)的仿真結(jié)果。從圖中可以明顯看出，隨著時(shí)間的推移，節(jié)點(diǎn)的鏈路有效性逐漸降低，當(dāng)n=200時(shí)，三條仿真曲線的鏈路有效性相差不大，接下來的遞減速度也放緩。n在0-50范圍內(nèi)時(shí)，不同初始位置的節(jié)點(diǎn)鏈路有效性隨著時(shí)間的遞增而迅速降低。到n=100以后，不同初始位置的節(jié)點(diǎn)鏈路有效性隨著時(shí)間的推移遞減的速度放緩。這說明初始位置對(duì)鏈路有效性的影響在節(jié)點(diǎn)移動(dòng)的剛開始一段時(shí)間，節(jié)點(diǎn)移動(dòng)的時(shí)間長了之后，初始位置對(duì)鏈路有效性的影響逐漸變小。
2.2 拓?fù)浣Y(jié)構(gòu)有效性
假定場(chǎng)景的節(jié)點(diǎn)密度為1/，dm為4，改變覆蓋半徑R的大小進(jìn)行仿真分析。如圖3所示為覆蓋半徑為4、8、16、32、64m時(shí)的仿真曲線圖，隨著節(jié)點(diǎn)移動(dòng)時(shí)間的推移，拓?fù)浣Y(jié)構(gòu)的有效性也在降低。覆蓋半徑越大，拓?fù)浣Y(jié)構(gòu)的有效性越高，遞減的幅度也越小。覆蓋半徑為4、8m時(shí)，拓?fù)浣Y(jié)構(gòu)有效性在節(jié)點(diǎn)剛開始移動(dòng)是呈現(xiàn)急劇降低現(xiàn)象，到n=50后，拓?fù)浣Y(jié)構(gòu)的有效性降低速度放緩。
3 結(jié)束語
無線移動(dòng)通信網(wǎng)絡(luò)作為當(dāng)前以及未來的主要網(wǎng)絡(luò)形式，其拓?fù)涞挠行躁P(guān)系到網(wǎng)絡(luò)運(yùn)行的穩(wěn)定和安全。拓?fù)鋱D中節(jié)點(diǎn)的無序移動(dòng)會(huì)影響到網(wǎng)絡(luò)的有效性，本文以理想狀態(tài)下的網(wǎng)絡(luò)運(yùn)行環(huán)境為背景建立了二維平面節(jié)點(diǎn)移動(dòng)模型，經(jīng)過仿真分析，研究節(jié)點(diǎn)初始位置、節(jié)點(diǎn)覆蓋半徑大小、節(jié)點(diǎn)密度等對(duì)拓?fù)涞挠行缘挠绊懀F(xiàn)實(shí)環(huán)境中的網(wǎng)絡(luò)拓?fù)涫艿降耐饨绺蓴_更多，其拓?fù)溆行赃€有待進(jìn)一步研究。
摘要:該文通過分析通信網(wǎng)絡(luò)中的拓?fù)鋬?yōu)化問題,抽象出數(shù)學(xué)模型,并利用遺傳算法對(duì)該模型進(jìn)行求解。最后通過實(shí)例驗(yàn)證用遺傳算法求解該問題明顯優(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)。
對(duì)通信網(wǎng)絡(luò)進(jìn)行優(yōu)化能夠使其更加快速有效可靠地傳遞信息,避免和最大限度減少因網(wǎng)絡(luò)中斷或延遲帶來的損失。遺傳算法(GA)模擬自然進(jìn)化過程,是一種具有并行特征的搜索算法,它能對(duì)解空間進(jìn)行搜索,加快對(duì)解的搜索速度,便于推廣到多結(jié)點(diǎn)的網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中,是解決大規(guī)模網(wǎng)絡(luò)優(yōu)化問題的有效工具。
1 遺傳算法求解過程
遺傳算法(GA)的主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作,具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力,自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間,自適應(yīng)調(diào)整搜索方向,不需要確定的規(guī)則。
使用遺傳算法求解通信網(wǎng)絡(luò)的拓?fù)鋬?yōu)化一般采用如圖1的過程。
2 算法設(shè)計(jì)
2.1 編碼和初始化種群
對(duì)于一個(gè)n結(jié)點(diǎn)的網(wǎng)絡(luò),其G圖最多有n(n-1)/2條邊,所以染色體的長度可定長為n(n-1)/2的二進(jìn)制串。由于鄰接矩陣具有對(duì)稱性,因此只需使用該矩陣的上三角表示,這樣可以使個(gè)體的長度為n(n-1)/2,壓縮比為2。 所求問題可用圖2的下(上)三角矩陣表示,稱其為G的鄰接矩陣T。如圖2。
圖2 G的鄰接矩陣T
在上述編碼方式中,則基因型可設(shè)為A[1,…,n(n-1)/2],由此可以生成W個(gè)基因個(gè)體,每個(gè)基因個(gè)體都是此通信網(wǎng)絡(luò)的一種拓?fù)洹?
2.2 根據(jù)個(gè)體適應(yīng)度進(jìn)行選擇
求解網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)模型屬于求解目標(biāo)函數(shù)最小值問題,適應(yīng)度函數(shù)可設(shè)為
隨著進(jìn)化代數(shù)的增加,個(gè)體適應(yīng)度之間的差別越來越小,可以對(duì)適應(yīng)度函數(shù)增加一個(gè)比例系數(shù)a將其放大,f’(x)=af(x),a>1。
2.3 算法終止條件
當(dāng)種群滿足以下三個(gè)條件之一時(shí)算法終止并輸出最優(yōu)解。
1) 個(gè)體的最大適應(yīng)度超過預(yù)先設(shè)定參數(shù)。
2) 個(gè)體的平均適應(yīng)度超過預(yù)先設(shè)定參數(shù)。
3) 種群代數(shù)超過預(yù)先設(shè)定參數(shù)。
3 實(shí)驗(yàn)及結(jié)果分析
某通信主干網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為9,經(jīng)過多次實(shí)驗(yàn)后,選取POP=60,Pc=0.65,Pm=0.01, 并以最大代數(shù)max gen=3000做為程序的終止條件。其各節(jié)點(diǎn)間線路代價(jià)如表1所示。
經(jīng)過該算法可得到計(jì)算結(jié)果如圖3。
若采用枚舉法,則時(shí)間復(fù)雜度為O(2N),此算法時(shí)間復(fù)雜度為O(N2),所以在對(duì)通信網(wǎng)絡(luò)優(yōu)化的同時(shí),大大降低了時(shí)間復(fù)雜度。
4 結(jié)論與總結(jié)
通信網(wǎng)絡(luò)的優(yōu)化是一個(gè)復(fù)雜且涉及范圍廣泛的課題,是通信網(wǎng)絡(luò)技術(shù)中不可缺少的部分。與遺傳算法相比,傳統(tǒng)算法比較復(fù)雜,局限性很大且計(jì)算時(shí)間較長。本文使用遺傳算法較好地解決了通信網(wǎng)絡(luò)優(yōu)化問題。本文提出的算法對(duì)小規(guī)模通信網(wǎng)絡(luò)的拓?fù)鋬?yōu)化問題能夠較好的求解,對(duì)大規(guī)模網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化還存在不足。改進(jìn)方法可以在遺傳算法中融合其它優(yōu)化算法,構(gòu)成一種混合遺傳算法。本文中對(duì)遺傳算法在網(wǎng)絡(luò)優(yōu)化中的研究只進(jìn)行了初步的探討,要將這種方法完善還需要做進(jìn)一步探討和研究。
