基于元胞遺傳算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)生存性研究

收稿日期：2014－04－24

基金項(xiàng)目：全國(guó)教育科學(xué)”十二五”規(guī)劃教育部規(guī)劃課題階段性研究成果(FJB110092)；國(guó)家自然科學(xué)基金(6107022905)；江蘇省軌道交通控制工程中心開(kāi)放基金(KFJ1312)。

作者簡(jiǎn)介：段謨意(1964-)，男，江西都昌人，學(xué)士，副教授，主要研究方向：網(wǎng)絡(luò)可靠性、信息安全；

王向中(1968-)，男，江蘇宜興人，碩士，副教授，主要研究方向：網(wǎng)絡(luò)可靠性、信息安全；

王應(yīng)喜(1964-)，男，江蘇南通人，碩士，副教授，主要研究方向：網(wǎng)絡(luò)可靠性、信息安全；

倪亞平（1966-），女，江蘇海門(mén)人，大專(zhuān)，執(zhí)業(yè)藥師，主要研究方向：計(jì)算機(jī)應(yīng)用；

王力群(1961-)，男，江蘇南京人，碩士，副教授，主要研究方向：網(wǎng)絡(luò)可靠性、信息安全。

摘要：生存性是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)可靠性的重要指標(biāo)之一。為此，基于元胞遺傳算法提出了一種新的評(píng)價(jià)方法（Cellular genetic algorithm， CGA）。該方法首先利用權(quán)重分布和最短路徑數(shù)建立了生存性的評(píng)價(jià)指標(biāo)，并且通過(guò)元胞遺傳以及元胞演化操作來(lái)實(shí)現(xiàn)最短路徑數(shù)的求解。同時(shí)，以實(shí)際數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，對(duì)比研究了本算法與SAIP算法之間的性能，結(jié)果表明CGA具有較好的適應(yīng)性。

關(guān)鍵詞：元胞遺傳算法； 生存性； 最短路徑； 權(quán)重分布； 關(guān)鍵節(jié)點(diǎn)

中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2014）03-0064-03

Research on Network Survivability based on Cellular Genetic Algorithm

DUANMoyi1，WANG Xiangzhong1，WANG Yingxi1，NI Yaping2， WANG Liqun1

(1 School of software engineering， Nanjing railway vocational and technical college， Nanjing 210031， China；

2 Logistics service group，China Medicine University， Nanjing 210009， China)

Abstract：Survivability is an important indicator of the reliability of wireless sensor network. Therefore， cellular genetic algorithm based on a new evaluation method is proposed (Cellular genetic algorithm， CGA) inthe paper. This method first uses the weight distribution and the shortest path to build the evaluation index of the survivability，and by cellular genetic and cellular evolution operations to achieve the solution of the shortest route number. At the same time， simulation experiment is carried out on the actual data in comparison with performance between this algorithm and SAIP algorithm， the results of which show that the CGA has better adaptability.

Key words：Cellular Genetic Algorithm; Survivability; Shortest Path; Weight Distribution; Key Node

0引言

生存性是在隨機(jī)破壞下系統(tǒng)的可靠性。生存性主要反映隨機(jī)性破壞和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)系統(tǒng)可靠性的影響。這里，隨機(jī)性破壞是指系統(tǒng)部件因?yàn)樽匀焕匣纫蛩囟斐傻淖匀皇?。隨著通信網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)的可靠性已日益受到來(lái)自多個(gè)方面的關(guān)注和重視［1］。網(wǎng)絡(luò)生存性作為衡量網(wǎng)絡(luò)可靠性的重要指標(biāo)，是指當(dāng)網(wǎng)絡(luò)中的鏈路和節(jié)點(diǎn)遭受攻擊或發(fā)生隨機(jī)失效時(shí)，網(wǎng)絡(luò)維持其基本通信功能的能力。目前，網(wǎng)絡(luò)生存性的研究主要集中在拓?fù)浣Y(jié)構(gòu)、路由策略和鏈路容量的優(yōu)化設(shè)計(jì)等方面，國(guó)內(nèi)外學(xué)者亦對(duì)此開(kāi)展了大量研究。馮冬芹等［1］為了提高工業(yè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的可靠性和可用性，使其能夠長(zhǎng)期自治地正常工作，提出了基于簇頭冗余的工業(yè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇路由算法。馬闖等［2］為了在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)可靠性研究中對(duì)故障檢測(cè)等容錯(cuò)機(jī)制進(jìn)行準(zhǔn)確評(píng)價(jià)和量化分析， 提出了一種具有高覆蓋度特點(diǎn)的網(wǎng)絡(luò)層次化故障模型。段謨意［3］ 通過(guò)建立克隆變異和克隆交叉操作規(guī)則，并結(jié)合模擬退火接受準(zhǔn)則來(lái)獲得退火溫度趨于零時(shí)的最優(yōu)解。趙攀等［4］通過(guò)建立生存性的評(píng)價(jià)指標(biāo)，同時(shí)針對(duì)失效狀態(tài)下的到達(dá)流量進(jìn)行小波變換，并利用混合蛙跳優(yōu)化小波系數(shù)，以此獲得最佳網(wǎng)絡(luò)剩余流量。朱曉娟等［5］從可靠性評(píng)估和可靠的數(shù)據(jù)傳輸技術(shù)兩個(gè)方面介紹了近年來(lái)的研究成果，對(duì)這些成果進(jìn)行了分類(lèi)、比較，并進(jìn)一步展望了在未來(lái)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)可靠性的研究方向。何明等［6］從拓?fù)渖伞⑼負(fù)溆霞巴負(fù)鋬?yōu)化三個(gè)方面論述了移動(dòng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的拓?fù)鋭?dòng)態(tài)演化性，但是這些優(yōu)化思想只是考慮了如何提高生存性技術(shù)本身的性能，卻并未從網(wǎng)絡(luò)模型和網(wǎng)絡(luò)狀態(tài)進(jìn)行量化研究，為此對(duì)提高網(wǎng)絡(luò)生存性的作用亦將十分有限。

針對(duì)上述存在的問(wèn)題，本文首先結(jié)合網(wǎng)絡(luò)權(quán)重和最短路徑數(shù)分布定義了網(wǎng)絡(luò)生存性指標(biāo)，而且通過(guò)元胞遺傳算法建立了等效最短路徑數(shù)的計(jì)算方法，同時(shí)又通過(guò)仿真實(shí)驗(yàn)深入研究了影響該指標(biāo)的重要因素。

1網(wǎng)絡(luò)生存性定義

在網(wǎng)絡(luò)通信過(guò)程中，節(jié)點(diǎn)之間一般以某條最短路徑進(jìn)行傳輸，跳數(shù)越多的路徑其可靠性越差，生存性也就越差。但網(wǎng)絡(luò)通信卻可能受到外界因素影響，進(jìn)而造成鏈路或者節(jié)點(diǎn)失效，此時(shí)若節(jié)點(diǎn)之間存在多條最短路徑，在某條最短路徑失效后則依然可以通過(guò)其它最短路徑傳輸數(shù)據(jù)。所以，節(jié)點(diǎn)之間的最短路徑數(shù)對(duì)于網(wǎng)絡(luò)生存性研究即具有高度重要且必要的作用。本文即結(jié)合最短路徑數(shù)和網(wǎng)絡(luò)權(quán)重分布來(lái)對(duì)網(wǎng)絡(luò)生存性進(jìn)行研究。

假設(shè)存在一n個(gè)節(jié)點(diǎn)的全連通網(wǎng)絡(luò)G(V， E)，其中的V表示點(diǎn)集，E表示邊集。根據(jù)文獻(xiàn)［7］的研究成果，節(jié)點(diǎn)i和j之間跳數(shù)小于等于r的值m(r)的計(jì)算公式則可表示為：

m(r)=∑rk=1(n-2)!(n-k-1)!(1)

而節(jié)點(diǎn)i和j之間跳數(shù)最少的路徑即稱(chēng)為最短路徑，此時(shí)對(duì)應(yīng)的跳數(shù)則為最短路長(zhǎng)。如果節(jié)點(diǎn)i和j之間存在k條最短路長(zhǎng)lij，那么可將其轉(zhuǎn)化為等效最短路徑數(shù)kij，具體公式為：

kij=km(lij)(2)

此時(shí)，如果G為全連通網(wǎng)絡(luò)，則kij=1。由理論來(lái)講，全連通網(wǎng)絡(luò)的生存性最優(yōu)，但是出于成本等因素考慮，實(shí)際過(guò)程中卻很少采用這種形式。由此可知，在非全連通網(wǎng)絡(luò)中，0

s1=2∑n-1i=1∑nj=i+1Kijn(n-1)(3)

解析公式（3）可知，該評(píng)價(jià)指標(biāo)僅僅基于等效最短路徑數(shù)來(lái)考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響，但由于實(shí)際鏈路帶寬等因素的不同作用，將導(dǎo)致每條鏈路上傳輸?shù)膯挝粯I(yè)務(wù)流也各不相同，因此對(duì)鏈路的權(quán)重因素也加以考慮，即顯得尤為重要。假設(shè)兩相鄰節(jié)點(diǎn)i和j之間的鏈路eij上對(duì)應(yīng)的權(quán)重為ωij，那么該權(quán)重對(duì)于網(wǎng)絡(luò)生存性的影響s2為：

s2=α1Bij+βCij(4)第3期段謨意，等：基于元胞遺傳算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)生存性研究智能計(jì)算機(jī)與應(yīng)用第4卷

其中，Bij為節(jié)點(diǎn)i和j之間的傳輸業(yè)務(wù)流大小，Cij為節(jié)點(diǎn)i和j之間的剩余帶寬，α和β為比例系數(shù)，且α+β=1。

基于以上兩點(diǎn)，本文將等效最短路徑數(shù)和網(wǎng)絡(luò)權(quán)重綜合起來(lái)加以考慮，即重新定義網(wǎng)絡(luò)生存性的評(píng)價(jià)指標(biāo)s：

s=s1ηs2θ=(2∑n-1i=1∑nj=i+1Kijn(n-1))η(α1Cij+βBij)θ(5)

其中，η和θ分別為(0， 1)之間的常系數(shù)，可用于度量等效最短路徑數(shù)和網(wǎng)絡(luò)權(quán)重對(duì)網(wǎng)絡(luò)生存性的影響程度。

針對(duì)上述評(píng)價(jià)指標(biāo)，本文采用元胞遺傳算法來(lái)對(duì)等效最短路徑數(shù)進(jìn)行研究。元胞遺傳算法是結(jié)合遺傳算法和元胞自動(dòng)機(jī)，使用元胞自動(dòng)機(jī)的演化規(guī)則來(lái)替換遺傳算法的進(jìn)化策略。其思想是：遺傳個(gè)體受到周?chē)従佑绊懞椭趁袂秩耄匀痪蜁?huì)具有與鄰居相似的多樣性。為保持向鄰居學(xué)習(xí)與殖民之間的平衡， 元胞遺傳算法則隨之而成為了解決復(fù)雜問(wèn)題的一種有效方法，藉此可以有效地減少計(jì)算最短路徑數(shù)的復(fù)雜度。

結(jié)合元胞遺傳算法，本文提出如下網(wǎng)絡(luò)生存性算法（Survivability Algorithm Based on Cellular Genetic，CGA），算法流程描述如下：

Step1：初始化網(wǎng)絡(luò)以及相關(guān)參數(shù)，并將網(wǎng)絡(luò)節(jié)點(diǎn)視作元胞，確定種群、元胞空間和元胞個(gè)體狀態(tài)；

Step2：選擇某一元胞為中心元胞，并從鄰域內(nèi)選擇出最優(yōu)元胞個(gè)體作為父體，用于產(chǎn)生下一代個(gè)體；

Step3：將選取的父體與中心元胞進(jìn)行交叉、變異操作，產(chǎn)生下一代個(gè)體，作為輔助種群；

Step4：根據(jù)元胞演化規(guī)則，確定下一代個(gè)體在下一時(shí)刻的狀態(tài)；

Step5：計(jì)算當(dāng)前的等效最短路徑數(shù)，與最優(yōu)解進(jìn)行比較，如果當(dāng)前解優(yōu)于最優(yōu)解，則用當(dāng)前解替換最優(yōu)解；

Step6：若當(dāng)前種群中每一個(gè)元胞個(gè)體操作完成，則采用輔助種群替換當(dāng)前種群，跳轉(zhuǎn)到Step 2；

Step7：判斷當(dāng)前種群是否已經(jīng)達(dá)到最大并且已經(jīng)搜索到最優(yōu)解，如果是則結(jié)束搜索，跳轉(zhuǎn)到Step 8，否則跳轉(zhuǎn)到Step 2；

Step8：輸出當(dāng)前最優(yōu)解，獲得等效最短路徑數(shù)；

Step9：根據(jù)式(5)獲得網(wǎng)絡(luò)生存性的評(píng)價(jià)指標(biāo)。

2數(shù)學(xué)仿真

針對(duì)上述提出的網(wǎng)絡(luò)生存性算法CGA，此處將給出數(shù)學(xué)仿真。首先，在OPNET中建立如圖1的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。并且初始化元胞遺傳算法參數(shù)相應(yīng)地設(shè)置為：鏈路容量20Mbps，延時(shí)12ms，各節(jié)點(diǎn)緩存大小為600 packets，數(shù)據(jù)包均為900Byte，權(quán)重分配系數(shù)α和β分別0.35和0.65。為了驗(yàn)證本文提出的CGA算法有效性，這里將與基于免疫規(guī)劃的模擬退火算法（Simulated Annealing algorithm based on Immune Programming，SAIP）進(jìn)行比較分析。SAIP算法僅僅考慮了最短路徑數(shù)，卻沒(méi)有考慮權(quán)重對(duì)網(wǎng)絡(luò)生存性的影響。將這兩種算法在OPNET中仿真800s時(shí)長(zhǎng)，獲得最后相對(duì)穩(wěn)定的100s結(jié)果進(jìn)行比較，仿真結(jié)果如圖2所示。從圖2可以看出，本文提出的CGA算法性能要優(yōu)于SAIP算法，算法精度較SAIP提高了5.64%。

圖1網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

Fig.1The network simulation topology

其次，本文分析不同權(quán)重系數(shù)θ下，減少網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)后網(wǎng)絡(luò)生存性的變化情況。同樣，定義減少的節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)為節(jié)點(diǎn)剔除比，在圖3中顯示了節(jié)點(diǎn)剔除比與網(wǎng)絡(luò)生存性之間的關(guān)系。從圖3可以看出，隨著節(jié)點(diǎn)剔除比的增加，網(wǎng)絡(luò)生存性整體上呈現(xiàn)出下降趨勢(shì)。在節(jié)點(diǎn)剔除比較小時(shí)，θ=0.6對(duì)應(yīng)曲線(xiàn)的網(wǎng)絡(luò)生存性要優(yōu)于θ=0.4的曲線(xiàn)，而節(jié)點(diǎn)剔除較大時(shí)情況卻發(fā)生了變化，θ=0.4所對(duì)應(yīng)曲線(xiàn)的網(wǎng)絡(luò)生存性則優(yōu)于θ=0.6的曲線(xiàn)。分析其原因在于，當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)遭到較小破壞時(shí)（節(jié)點(diǎn)失效數(shù)目較少），權(quán)重的變化比網(wǎng)絡(luò)結(jié)構(gòu)變化受到的影響要小。而在后期，由于失效節(jié)點(diǎn)的數(shù)目增多，流量減少的程度則迅速增加，權(quán)重受到影響程度也隨之加大，使得狀態(tài)發(fā)生突變。

圖2網(wǎng)絡(luò)生存性比較

Fig.2The comparison of network survivability

圖3網(wǎng)絡(luò)生存性與節(jié)點(diǎn)剔除比的關(guān)系

Fig.3The relationship between network

survivability and node removed ratio

這里還要對(duì)CGA算法的影響因素進(jìn)行深入分析。將網(wǎng)絡(luò)生存性評(píng)價(jià)指標(biāo)I中的網(wǎng)絡(luò)權(quán)重系數(shù)θ作為研究對(duì)象，分析在不同的網(wǎng)絡(luò)權(quán)重系數(shù)θ下的網(wǎng)絡(luò)生存性的變化情況，結(jié)果如圖4所示。從圖4的整體情況上來(lái)看，θ=0.6對(duì)應(yīng)曲線(xiàn)的網(wǎng)絡(luò)生存性在仿真初期要優(yōu)于θ=0.4的曲線(xiàn)，但是在仿真后期則要劣于θ=0.4這條曲線(xiàn)。這就說(shuō)明在仿真初期，權(quán)重系數(shù)θ越大，對(duì)應(yīng)的網(wǎng)絡(luò)生存性越好，而在后期網(wǎng)絡(luò)生存性權(quán)重系數(shù)θ越小，對(duì)應(yīng)的網(wǎng)絡(luò)生存性則會(huì)越好。

圖4不同網(wǎng)絡(luò)權(quán)重系數(shù)下網(wǎng)絡(luò)生存性比較

Fig.4The comparison of network survivability

in different network weight factor

3結(jié)束語(yǔ)

本文結(jié)合元胞遺傳算法提出了一種新的網(wǎng)絡(luò)生存性刻畫(huà)方法。該方法結(jié)合最短路徑數(shù)和網(wǎng)絡(luò)權(quán)重分布建立生存性評(píng)價(jià)指標(biāo)，并且通過(guò)定義元胞演化規(guī)則和選擇、交叉、變異操作來(lái)模擬元胞狀態(tài)的變化，以此反映網(wǎng)絡(luò)生存性的優(yōu)劣。同時(shí)，本文將提出的CGA算法與SAIP算法進(jìn)行仿真分析，說(shuō)明了該方法的有效性，并且深入分析了網(wǎng)絡(luò)生存性的影響因素。在后續(xù)研究中，可以考慮利用元胞蟻群、人工免疫等算法，針對(duì)網(wǎng)絡(luò)生存性和有效性進(jìn)行建模，以此形成一套比較完整的網(wǎng)絡(luò)可靠性評(píng)價(jià)指標(biāo)。

參考文獻(xiàn)：

［1］馮冬芹，李光輝，全劍敏，等.基于簇頭冗余的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)可靠性研究［J］.浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2009(5):849-854.

［2］馬闖，劉宏偉，左德承，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的層次化故障模型［J］.清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011(S1):3002-3005.

［3］段謨意.基于免疫克隆模擬退火算法的網(wǎng)絡(luò)生存性研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012(12): 1008-1012.

［4］趙攀，魏正曦，張弘.網(wǎng)絡(luò)生存性計(jì)算方法以及性能評(píng)價(jià)［J］.計(jì)算機(jī)應(yīng)用，2013(10):998-1002.

［5］朱曉娟，陸陽(yáng)，邱述威，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸可靠性研究綜述［J］.計(jì)算機(jī)科學(xué)，2013(9):1120-1124.

［6］何明，梁文輝，陳國(guó)華，等.水下移動(dòng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)洌跩］.控制與決策，2013(12):3004-3007.

［7］段謨意.網(wǎng)絡(luò)抗毀性及其評(píng)價(jià)指標(biāo)研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013(11):2553-2557.