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

收稿日期：2014－04－24

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

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

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

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

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

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

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

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

中圖分類號：TP393文獻標識碼：A文章編號：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引言

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

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

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

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

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

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

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

kij=km(lij)(2)

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

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

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

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

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

基于以上兩點，本文將等效最短路徑數(shù)和網(wǎng)絡權重綜合起來加以考慮，即重新定義網(wǎng)絡生存性的評價指標s：

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

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

針對上述評價指標，本文采用元胞遺傳算法來對等效最短路徑數(shù)進行研究。元胞遺傳算法是結(jié)合遺傳算法和元胞自動機，使用元胞自動機的演化規(guī)則來替換遺傳算法的進化策略。其思想是：遺傳個體受到周圍鄰居影響和殖民侵入，自然就會具有與鄰居相似的多樣性。為保持向鄰居學習與殖民之間的平衡， 元胞遺傳算法則隨之而成為了解決復雜問題的一種有效方法，藉此可以有效地減少計算最短路徑數(shù)的復雜度。

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

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

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

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

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

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

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

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

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

Step9：根據(jù)式(5)獲得網(wǎng)絡生存性的評價指標。

2數(shù)學仿真

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

圖1網(wǎng)絡拓撲結(jié)構圖

Fig.1The network simulation topology

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

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

Fig.2The comparison of network survivability

圖3網(wǎng)絡生存性與節(jié)點剔除比的關系

Fig.3The relationship between network

survivability and node removed ratio

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

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

Fig.4The comparison of network survivability

in different network weight factor

3結(jié)束語

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

參考文獻：

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

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

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

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

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

［6］何明，梁文輝，陳國華，等.水下移動無線傳感器網(wǎng)絡拓撲［J］.控制與決策，2013(12):3004-3007.

［7］段謨意.網(wǎng)絡抗毀性及其評價指標研究［J］.小型微型計算機系統(tǒng)，2013(11):2553-2557.