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

查道貴，許彩芳

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

?

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

查道貴，許彩芳

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

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

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

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

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

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

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

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

2 問(wèn)題描摹

2.1 問(wèn)題假設(shè)

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

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

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

(1)

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

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

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

(2)

(3)

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

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

(4)

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

如果計(jì)算機(jī)網(wǎng)絡(luò)狀態(tài)為可用，則處于網(wǎng)絡(luò)狀態(tài)的計(jì)算機(jī)結(jié)點(diǎn)皆相互連通，各可用狀態(tài)的結(jié)點(diǎn)能組成一棵生成樹(shù)，網(wǎng)絡(luò)互聯(lián)正常并能確保正常工作。在正常運(yùn)行的互聯(lián)網(wǎng)過(guò)程中，在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ì)算機(jī)網(wǎng)絡(luò)為正常工作狀態(tài)，那么互聯(lián)網(wǎng)中數(shù)據(jù)傳輸最大化為R,而且C≤C0,此時(shí)網(wǎng)絡(luò)為正常工作狀態(tài)，用方程式表示為：

(6)

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

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

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

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

(7)

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

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

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

3.2 求解過(guò)程

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

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

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

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

3.3.1 基因表達(dá)

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

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

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

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

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

3.3.2 選擇適值函數(shù)

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

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

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

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

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

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

②依照數(shù)據(jù)變異基因數(shù)目，對(duì)整數(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è)條件，選擇時(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，依照遺傳算法計(jì)算與分析要求，使gij=1；

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

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

4 仿真舉例

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

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

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

5 結(jié) 語(yǔ)

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

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

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

[1]江逸楠，李瑞瑩，黃寧，等．網(wǎng)絡(luò)可靠性評(píng)估方法綜述[J]．計(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]．計(jì)算機(jī)技術(shù)與發(fā)展，2007(1)：63-68

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

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

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

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

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

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

2015-08-21

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

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

TP393.02

：A

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

10.3969/j.issn.1673-2006.2015.12.025