查道貴，許彩芳

宿州職業(yè)技術(shù)學(xué)院計算機(jī)信息系，安徽宿州，234101

?

基于遺傳算法的計算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化分析

查道貴，許彩芳

宿州職業(yè)技術(shù)學(xué)院計算機(jī)信息系，安徽宿州，234101

利用遺傳算法建模，分析排隊(duì)通信數(shù)據(jù)模型并計算容量分配和路由選擇時間；采用遺傳算法和遍歷配法競爭選擇，確定適應(yīng)值函數(shù)與范圍，得到相關(guān)的收斂的探索方式。利用遺傳運(yùn)算對計算機(jī)網(wǎng)絡(luò)進(jìn)行優(yōu)化并調(diào)整數(shù)據(jù)傳輸，判斷信道連通性。仿真結(jié)果表明：遺傳算法具有搜索高效、求解便捷和算法結(jié)構(gòu)簡便等優(yōu)勢，對全局進(jìn)行計算時，能夠得到最優(yōu)近似值。

計算機(jī)網(wǎng)絡(luò)；遺傳算法；可靠度；優(yōu)化

所謂計算機(jī)網(wǎng)絡(luò)可靠性是指在操作方式、負(fù)載條件、維修方式、濕度、溫度和輻射等規(guī)定條件下，一個季度或者1 000小時等規(guī)定時間內(nèi)，計算機(jī)網(wǎng)絡(luò)滿足通信要求與保持連通的能力。計算機(jī)網(wǎng)絡(luò)可靠性的測試通常包括網(wǎng)絡(luò)生存性、連通性，在多種模式中網(wǎng)絡(luò)元件有效性和抗破壞性等方面內(nèi)容[1]。

國外對計算機(jī)網(wǎng)絡(luò)可靠性的研究最早源自電信網(wǎng)絡(luò)交換的研究，并將網(wǎng)絡(luò)的連通性作為計算機(jī)網(wǎng)絡(luò)可靠性的測度。國內(nèi)對計算機(jī)網(wǎng)絡(luò)可靠性的研究最早由著名科學(xué)家錢學(xué)森提出，但主要應(yīng)用于軍工領(lǐng)域，1956年張公緒提出通信網(wǎng)絡(luò)割集的概念和算法。之后，更多國內(nèi)外科研人員、專家學(xué)者開始研究這個課題，出現(xiàn)了許多新的算法，如不交和算法、因子分解算法、完全狀態(tài)枚舉算法、容斥原理算法等。

1 計算機(jī)網(wǎng)絡(luò)可靠度

計算機(jī)網(wǎng)絡(luò)可靠度與計算機(jī)網(wǎng)絡(luò)的可靠性不同，它是指在操作方式、負(fù)載條件、維修方式、濕度、溫度和輻射等規(guī)定條件下與一個季度、1 000小時等規(guī)定時間內(nèi)，計算機(jī)網(wǎng)絡(luò)對規(guī)定功能予以完成的概率。

如何提高和優(yōu)化計算機(jī)網(wǎng)絡(luò)的可靠度，是計算機(jī)網(wǎng)絡(luò)使用與研究關(guān)注的重要問題。本研究根據(jù)順序服務(wù)措施和原則利用遺傳算法建立數(shù)學(xué)模型，忽略延時并簡化計算機(jī)網(wǎng)絡(luò)中通信NP難題(非圖靈機(jī)上的多項(xiàng)式時間算法問題)與存儲節(jié)點(diǎn)信息，得到收斂的相近的最佳結(jié)果。

2 問題描摹

2.1 問題假設(shè)

(1)假設(shè)在網(wǎng)絡(luò)中的傳輸節(jié)點(diǎn)間只有一條直線傳輸鏈路，卻存在有多條信息傳輸信道，由此方便通過建立數(shù)學(xué)模型來對網(wǎng)絡(luò)傳輸?shù)男畔⑦M(jìn)行描述；(2)假定各傳輸信道的穩(wěn)定性良好，且各節(jié)點(diǎn)能有效進(jìn)行數(shù)據(jù)信息的傳輸；(3)網(wǎng)絡(luò)中的信道介質(zhì)長度與網(wǎng)絡(luò)可靠度存在間接數(shù)據(jù)交換關(guān)系；(4)在設(shè)備出現(xiàn)故障時，與數(shù)據(jù)傳輸信道無關(guān)，即通信信道與網(wǎng)絡(luò)有故障與工作兩種狀態(tài)[2]。

2.2 建立數(shù)學(xué)模型

計算機(jī)網(wǎng)絡(luò)信道鏈路中的成本矩陣可用方程式表示：

(1)

其中，Cij表示結(jié)點(diǎn)j,i表示間鏈路介質(zhì)成本,C0表示信道介質(zhì)成本矩陣。

用數(shù)學(xué)計算公式表示網(wǎng)絡(luò)信道鏈路介質(zhì)見方程式(2)和(3)：

Diαij(i,j=1,…,N)

(2)

(3)

以上兩個公式中，N表示計算機(jī)網(wǎng)絡(luò)傳遞結(jié)點(diǎn)數(shù)，C表示通信信道中信息的成本，Diαij表示結(jié)點(diǎn)j和i間鏈路介質(zhì)數(shù)，β、α表示結(jié)點(diǎn)可靠度在計算機(jī)網(wǎng)絡(luò)中的約束常數(shù)。如果gij=1，那么節(jié)點(diǎn)j和i間存在直線鏈路；如果gij=0，那么以上兩節(jié)點(diǎn)不存在直接鏈路。

依照以上計算方法，計算鏈路介質(zhì)的方程式為：

(4)

其中，rji表示網(wǎng)絡(luò)結(jié)點(diǎn)間鏈路可靠度(1≤i≤m，1≤j≤n)，R0表示網(wǎng)絡(luò)可靠度矩陣[3]。

如果計算機(jī)網(wǎng)絡(luò)狀態(tài)為可用，則處于網(wǎng)絡(luò)狀態(tài)的計算機(jī)結(jié)點(diǎn)皆相互連通，各可用狀態(tài)的結(jié)點(diǎn)能組成一棵生成樹，網(wǎng)絡(luò)互聯(lián)正常并能確保正常工作。在正常運(yùn)行的互聯(lián)網(wǎng)過程中，在L′?L成立的狀態(tài)下，互聯(lián)網(wǎng)線路能夠正常傳輸信息。在這種情況下，互聯(lián)網(wǎng)中所有結(jié)點(diǎn)均為正常工作狀態(tài)，其可靠度表示為：

(5)

其中，ni表示網(wǎng)絡(luò)第i結(jié)點(diǎn)，P(ni)表示網(wǎng)絡(luò)鏈路中介質(zhì)可靠度，N表示網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)。

在方程式(4)中，如果計算機(jī)網(wǎng)絡(luò)為正常工作狀態(tài)，那么互聯(lián)網(wǎng)中數(shù)據(jù)傳輸最大化為R,而且C≤C0,此時網(wǎng)絡(luò)為正常工作狀態(tài)，用方程式表示為：

(6)

其中，li表示網(wǎng)絡(luò)中第i條線路介質(zhì)，Ω表示正常工作狀態(tài)下計算機(jī)網(wǎng)絡(luò)的所有集合[4]。

3 基于遺傳算法的計算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化

3.1 通信過程優(yōu)化的數(shù)學(xué)建模

在信道中，為優(yōu)化數(shù)據(jù)傳遞，簡化計算機(jī)網(wǎng)絡(luò)中通信NP難題與存儲節(jié)點(diǎn)信息，根據(jù)順序服務(wù)措施及原則，應(yīng)用遺傳算法建立數(shù)學(xué)模型。計算分析數(shù)據(jù)排隊(duì)模型，為方便描述節(jié)點(diǎn)信息傳輸與信道鏈路信息處理的延時忽略，用方程式(7)表示容量分配與路由選擇的時間計算：

(7)

其中，K表示可選容量類型數(shù)，λm表示互聯(lián)網(wǎng)節(jié)點(diǎn)m報文送達(dá)率，fk表示信息流量，D表示企業(yè)信息傳遞延時，Vk表示信息流量的更改。

然而，方程式(7)中，其約束條件還有以下幾點(diǎn)，需要優(yōu)化多信道傳輸可靠度：

運(yùn)用方程式(7)可獲得一個非線性方程，該方程含有分配容量與選擇路由，屬于有約束條件且優(yōu)化后的數(shù)學(xué)建模模型，可見，采用遺傳算法能夠解決該問題。

3.2 求解過程

遺傳算法是一種隨機(jī)搜索算法，它是通過遺傳機(jī)理和生物自然選擇理念而得出的并以交換個體信息與群體搜索的方式，搜索出互聯(lián)網(wǎng)中最優(yōu)點(diǎn)且可確保算法設(shè)計最優(yōu)化。具體過程如下：

Begin：i←0初始化，p(i)計算，p(i)若條件不滿足，則需要終止條件→begin→p(i)重組，獲得c(i)→計算c(i)→從c(i)與p(i)中對p(i+1)進(jìn)行選擇→i←i+1→end

3.3 優(yōu)化設(shè)計

依照遺傳算法優(yōu)化計算機(jī)網(wǎng)絡(luò)可靠性，可以滿足優(yōu)化互聯(lián)網(wǎng)的需求，且能夠達(dá)到較好效率。該方法可以明顯改善互聯(lián)網(wǎng)數(shù)據(jù)傳輸效率，在具體設(shè)計中，首先將遺傳算法控制參數(shù)與相關(guān)數(shù)據(jù)輸入，確定初始群體適應(yīng)值函數(shù)與范圍，利用遍歷匹配法來競爭選擇，再實(shí)施雜交處理且必須滿足與全局相近的有收斂條件的最優(yōu)解[5]。

3.3.1 基因表達(dá)

從根本上說，基因表達(dá)是對互聯(lián)網(wǎng)傳輸予以確定的主要優(yōu)勢，本研究通過二進(jìn)制一維編碼，對計算機(jī)互聯(lián)網(wǎng)N個結(jié)點(diǎn)互聯(lián)網(wǎng)基因予以確定，具體設(shè)計見表1。

圖1 基因結(jié)點(diǎn)網(wǎng)絡(luò)圖

表1 計算機(jī)互聯(lián)網(wǎng)基因結(jié)點(diǎn)

假定互聯(lián)網(wǎng)信道傳輸中有4個結(jié)點(diǎn)(n1,n2,n3,n4)，則將這4個互聯(lián)網(wǎng)基因結(jié)點(diǎn)會轉(zhuǎn)化為一個基因，見表2，從而形成一個網(wǎng)絡(luò)結(jié)構(gòu)圖，見圖1。

表2 4個節(jié)點(diǎn)的互聯(lián)網(wǎng)基因結(jié)點(diǎn)

3.3.2 選擇適值函數(shù)

算法確定的基礎(chǔ)是適值函數(shù)。適值函數(shù)對遺傳算法中發(fā)生的數(shù)據(jù)欺騙可以有效預(yù)防，以降序的方式對數(shù)據(jù)個體在初始種群中的成本值進(jìn)行排列，設(shè)定最小排序成本個體編碼值為1，設(shè)定最大排序成本編碼值為POP-size,那么其適值函數(shù)用方程(x-1)/(POP-size-1)=f(x)表示。在該公式中，POP-size表示種群規(guī)模，x表示網(wǎng)絡(luò)成本中數(shù)據(jù)個體的排序位置，且其約束條件是POP-size≥x≥1。

3.3.3 網(wǎng)絡(luò)優(yōu)化中的遺傳運(yùn)算

遺傳運(yùn)算在對計算機(jī)網(wǎng)絡(luò)優(yōu)化中主要分為變異與交叉兩種形式。

(1)交叉。([1,N])是實(shí)現(xiàn)數(shù)據(jù)交叉的范圍,采用隨機(jī)交叉法確定基因交叉位置且實(shí)現(xiàn)數(shù)據(jù)交換，能確保計算機(jī)網(wǎng)絡(luò)數(shù)據(jù)互連互通性，但有時一些臨界數(shù)據(jù)并不說明網(wǎng)絡(luò)數(shù)據(jù)連通，會發(fā)生網(wǎng)絡(luò)錯誤，因此應(yīng)對算法進(jìn)行調(diào)整。

(2)變異。首先明確變異的基因范圍和具體變異數(shù)目，再依照所選基因片段取代原先基因。具體操作包括以下幾步：

①如果數(shù)據(jù)變異基因是x，那么x=[x1，x2，…，xk];

②依照數(shù)據(jù)變異基因數(shù)目，對整數(shù)進(jìn)行隨機(jī)選取，k∈[1,n],u∈[1,n];

④若不能實(shí)現(xiàn)步驟③，可以轉(zhuǎn)至步驟②[6]。

3.3.4 進(jìn)化運(yùn)算

運(yùn)用轉(zhuǎn)輪選擇運(yùn)算并依照適值函數(shù)運(yùn)算法提出相關(guān)假設(shè)條件，選擇時，任意基因選擇概率均與其適值呈正比，適值是fk的基因。適值fk和選擇概率Pk及與種群編碼排序范圍的關(guān)系用方程式表示為：

3.3.5 算法優(yōu)化調(diào)整

依照算法優(yōu)化結(jié)果，調(diào)整相應(yīng)數(shù)據(jù)傳輸，分析算法中所有基因表達(dá)式，以此判斷信道是否連通[7]。

①若gij=1,那么執(zhí)行原交叉，實(shí)施基因數(shù)據(jù)變異，最終完成數(shù)據(jù)操作；

②若gij=0，依照遺傳算法計算與分析要求，使gij=1；

③若gij=1，實(shí)施數(shù)據(jù)交換，使gij=0;

④若無法實(shí)現(xiàn)步驟③,那么需要判斷與測試網(wǎng)絡(luò)信道的連通性。

4 仿真舉例

依照以上遺傳算法計算，并根據(jù)假設(shè)，構(gòu)建計算機(jī)網(wǎng)絡(luò)通信系統(tǒng)，運(yùn)用遺傳算法進(jìn)行仿真實(shí)驗(yàn)。如果計算機(jī)網(wǎng)絡(luò)系統(tǒng)結(jié)點(diǎn)有6個，以實(shí)驗(yàn)的方式優(yōu)化計算機(jī)網(wǎng)絡(luò)可信度，多次計算實(shí)驗(yàn)結(jié)果。在計算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化實(shí)驗(yàn)中應(yīng)用遺傳算法，使網(wǎng)絡(luò)穩(wěn)定性與可靠性得到有效提升，所得結(jié)果見如下矩陣：

運(yùn)用可靠度矩陣R0對所測可靠度數(shù)據(jù)進(jìn)行計算[8]，計算得出的結(jié)果見如下矩陣 ：

依照上文的假設(shè)可得出：計算機(jī)網(wǎng)絡(luò)結(jié)點(diǎn)N為6，優(yōu)化互聯(lián)網(wǎng)通信信道可靠度約束常數(shù)：β=2，α=2。計算互聯(lián)網(wǎng)通信信道時，如果遺傳操作代數(shù)是100次，對其進(jìn)行仿真計算求解，能夠?qū)⒒ヂ?lián)網(wǎng)信道鏈路總成本計算出來，最終計算得出其值為46，可以確保網(wǎng)絡(luò)信道可靠度max為0.885，互聯(lián)網(wǎng)系統(tǒng)信息傳輸具有較為可靠的安全性與完整性。這充分表明，在網(wǎng)絡(luò)信道可靠度的優(yōu)化中，利用遺傳算法可以滿足互聯(lián)網(wǎng)信息傳輸需求。

5 結(jié) 語

與其他算法相比較，遺傳算法有以下特點(diǎn)：

(1)遺傳算法可以提升信息傳輸速度。通過仿真實(shí)驗(yàn)與實(shí)際計算分析，遺傳算法具有較為簡單的結(jié)構(gòu)，在互聯(lián)網(wǎng)信息傳輸中比較適用。尤其本身具有搜索高效、操作簡單以及適用性強(qiáng)等特點(diǎn)，可以確?；ヂ?lián)網(wǎng)傳輸效率的有效提升。與傳統(tǒng)互聯(lián)網(wǎng)傳輸計算方法相比，遺傳算法的優(yōu)勢較為明顯，運(yùn)用該算法，互聯(lián)網(wǎng)計算時間得到有效縮短，進(jìn)一步提高了信息計算速度且優(yōu)化了計算效果；能明顯改善互聯(lián)網(wǎng)傳輸方式，有效地提高互聯(lián)網(wǎng)操作性能。

(2)遺傳算法具有較強(qiáng)的計算信息傳輸?shù)倪m用性。遺傳算法大大降低了互聯(lián)網(wǎng)成本，在原有基礎(chǔ)上，不斷提升網(wǎng)絡(luò)可信度，對互聯(lián)網(wǎng)性能進(jìn)行不斷優(yōu)化，而且還能兼顧矩陣可靠度優(yōu)化問題、鏈路介質(zhì)成本問題和數(shù)學(xué)模型求解等相關(guān)問題。

[1]江逸楠，李瑞瑩，黃寧，等．網(wǎng)絡(luò)可靠性評估方法綜述[J]．計算機(jī)科學(xué)，2012，39(5)：9-18

[2]吳俊，段東立，趙娟，等．網(wǎng)絡(luò)系統(tǒng)可靠性研究現(xiàn)狀與展望[J]．復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8(2)：77-86

[3]劉東，丁照宇．基于改進(jìn)遺傳算法的可靠性網(wǎng)絡(luò)優(yōu)化設(shè)計[J]．計算機(jī)技術(shù)與發(fā)展，2007(1)：63-68

[4]武小悅，張維明，沙基昌．具有節(jié)點(diǎn)失效的網(wǎng)絡(luò)可靠度的信息交互算法[J]．國防科技大學(xué)學(xué)報，1999(2)：111-114

[5]金慶風(fēng)，劉勝利．基于可靠性理論的計算機(jī)通信網(wǎng)絡(luò)分析及多目標(biāo)優(yōu)化[J]．微型電腦應(yīng)用，2009(1)：19-73

[6]孫力娟，王汝傳．量子計算與遺傳算法的融合及其在計算機(jī)通信網(wǎng)優(yōu)化中的應(yīng)用[J]．電子與信息學(xué)報，2007(4)：920-923

[7]劉雅琴，遲洪欽．最優(yōu)合并構(gòu)成的有序遺傳算法[J]．上海師范大學(xué)學(xué)報:自然科學(xué)版，2001(4)：89-92

[8]肖宇峰，張華．基于二元決策圖的節(jié)點(diǎn)不可靠網(wǎng)絡(luò)可靠度計算[J]．計算機(jī)工程，2015，41(1)：87-91

(責(zé)任編輯：汪材印)

2015-08-21

安徽省教育廳自然科學(xué)研究項(xiàng)目“皖北旱地小麥秸稈腐化劑選擇及直接還田配套技術(shù)的研究”(KJ2014A254)。

查道貴(1975-)，安徽安慶人，碩士，講師，主要研究方向：計算機(jī)應(yīng)用。

TP393.02

：A

：1673-2006(2015)12-0093-04

10.3969/j.issn.1673-2006.2015.12.025