段謨意

（南京鐵道職業(yè)技術(shù)學(xué)院 軟件學(xué)院，江蘇 南京210031）

0 引 言

網(wǎng)絡(luò)生存性作為網(wǎng)絡(luò)可靠性的重要衡量指標(biāo)，它主要應(yīng)用于隨機(jī)破壞作用下的網(wǎng)絡(luò)可靠性研究，包括受到攻擊后的網(wǎng)絡(luò)剩余通信能力以及損失程度。目前針對通信網(wǎng)絡(luò)的生存性討論是網(wǎng)絡(luò)可靠性領(lǐng)域的研究熱點(diǎn)［1－3］。對此，國內(nèi)外學(xué)者進(jìn)行了大量工作。文獻(xiàn) ［4］針對網(wǎng)絡(luò)最大流建立了獲取傳感器網(wǎng)絡(luò)最大生存時間確切值的算法。文獻(xiàn) ［5］通過綜合考慮通信網(wǎng)絡(luò)的業(yè)務(wù)量影響因素和連通性，提出了網(wǎng)絡(luò)可靠性評價測度?；矢サ龋?］定義了網(wǎng)絡(luò)生存性指標(biāo)，并基于災(zāi)害條件對具有SDH自愈環(huán)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)生存性進(jìn)行了定量分析。在保證網(wǎng)絡(luò)連通性的前提下，文獻(xiàn)［7］通過減少網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗來延長整個網(wǎng)絡(luò)的生存時間。文獻(xiàn) ［8］通過綜合考慮同時滿足時延性和可靠性需求，重點(diǎn)分析了網(wǎng)絡(luò)層與MAC層對通信范圍的要求。文獻(xiàn) ［9］通過采用節(jié)點(diǎn)刪除法比較了刪除節(jié)點(diǎn)前后的網(wǎng)絡(luò)性能變化，但存在網(wǎng)絡(luò)不連通和生存性計算不精確的缺陷。

針對上述問題，本文首先定義了網(wǎng)絡(luò)生存性，并且通過免疫克隆模擬退火算法建立了網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量的計算方法，同時通過仿真實驗深入研究了該方法的有效性。

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

假設(shè)存在如圖1所示的通信網(wǎng)絡(luò)G （V，E，F(xiàn)），其中，V表示點(diǎn)集，E＝ （eij）表示邊集，F(xiàn)＝ （fij）表示網(wǎng)絡(luò)中任意兩點(diǎn)之間的流量，即fij表示節(jié)點(diǎn)Vi和Vj之間的流量。

對于網(wǎng)絡(luò)生存性存在很多定義指標(biāo)，這里將網(wǎng)絡(luò)生存性指標(biāo)定義為某些鏈路在失效情況下，網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸能力與正常情況下網(wǎng)絡(luò)數(shù)據(jù)傳輸能力的比例。假設(shè)網(wǎng)絡(luò)中存在n段鏈路，鏈路i對應(yīng)的權(quán)重為ωi，并且所有鏈路出現(xiàn)故障的概率相等，正常情況下網(wǎng)絡(luò)數(shù)據(jù)傳輸量為f，有k條鏈路失效情況下的網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量為f （k），其中，k的最大取值應(yīng)保證整個網(wǎng)絡(luò)連通 （令其最大值為K）。由于n條鏈路中有m條鏈路失效的可能為，故網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f （k）可表示為

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

那么，網(wǎng)絡(luò)的生存性則可定義為

在上述定義中，關(guān)鍵在于求解網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f（k）。本文首先結(jié)合模擬退火算法［10］提出了如下評價網(wǎng)絡(luò)生存性算法：

步驟1 初始化網(wǎng)絡(luò)G，隨機(jī)產(chǎn)生退火初始溫度tj和網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f （k）的初始解xj（此時令j＝0），以及溫度冷卻系數(shù)R （R為0或者1）；

步驟2 如果在f（k）的初始解xj的領(lǐng)域內(nèi)存在新的可行解x′j，計算當(dāng)前這兩個解的函數(shù)差 Δy，Δy＝y(tǒng)（x′j）－y （xj）；

步驟3 根據(jù)Metropolis準(zhǔn)則，如果Δy＜0，則接受xj作為f （j）的當(dāng)前最優(yōu)解；

步驟5 執(zhí)行退火操作，令tj＋1＝R＊tj，j＝j(luò)＋1；

步驟6 跳轉(zhuǎn)到步驟2，直至達(dá)到該溫度下的熱平衡狀態(tài)，輸出當(dāng)前最優(yōu)解作為網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f（j）的最終解；

步驟7 根據(jù)式 （2）計算網(wǎng)絡(luò)的生存性s；

步驟8 算法結(jié)束。

模擬退火算法通過控制初溫和降溫來獲得最優(yōu)解。當(dāng)處于高溫時模擬退火算法可以避免陷入局部極值，而處于低溫時能夠較好進(jìn)行保優(yōu)，但卻存在收斂時間過長、效率不高等缺點(diǎn)。同時，免疫克隆算法通過模擬免疫系統(tǒng)的多克隆機(jī)理，并基于對抗原反應(yīng)的特性來增加克隆的多樣性，減少搜索時間。因此，本文結(jié)合模擬退火算法和免疫克隆算法對網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f （k）進(jìn)行研究。

2 SAICSA算法描述

免疫克隆模擬退火算法［11］基于親和度函數(shù)來將當(dāng)前解分裂成多個相同點(diǎn)，并通過變異、交叉和選擇來獲得新的抗體群。同時，在變異和交叉過程中，采用模擬退火接受準(zhǔn)則來決定是否接受新的抗體。當(dāng)溫度趨于零時獲得系統(tǒng)的最優(yōu)解。

本文提出的SAICSA （survivability algorithm based on immune clonal simulated annealing）算法描述如下：

步驟1 初始化網(wǎng)絡(luò)參數(shù)，確定抗體群A，以及種群規(guī)模W，變異概率p1，交叉概率p2，初始溫度t0等參數(shù)；

步驟2 根據(jù)式 （3）計算抗體群中每個抗體的親和度z（xk），用來表示抗體與抗原之間的匹配程度

其中，k＝1，2，…，W；

步驟3 根據(jù)式 （4）將第k個抗體進(jìn)行克隆，得到規(guī)模為Wr的新抗體群B

式中：β——克隆系數(shù)，int（）——取整函數(shù)；

步驟4 按照以下規(guī)則對新抗體群B進(jìn)行克隆變異操作，產(chǎn)生臨時抗體群C：

（1）根據(jù)式 （5）計算產(chǎn)生父抗體b的子抗體b＇

其中，poisscdf（）為泊松分布函數(shù)；

（2）計算抗體b和b＇的親和度z （b）和z （b＇），令Δz＝z （b＇）－z （b），如果則接受b＇作為當(dāng)前最優(yōu)解，否則仍然將b作為當(dāng)前最優(yōu)解。

步驟5 按照以下規(guī)則對抗體C進(jìn)行克隆交叉操作，產(chǎn)生新的抗體群A＇；

（1）產(chǎn)生 ［0，1］內(nèi)的泊松分布隨機(jī)數(shù)ε，如果ε＜p2，則按照式 （6）和式 （7）對父抗體b1和b2進(jìn)行交叉操作獲得 子抗體b1＇和b2＇

（2）根據(jù)步驟4中的第 （2）步，判斷是否接受交叉后的子抗體b1＇和b2＇。

步驟6 當(dāng)tk＝0時，退火過程結(jié)束，跳轉(zhuǎn)到步驟8；

步驟7 否則，令k＝k＋1，tk＋1＝tk（1－k／B），跳轉(zhuǎn)到步驟2，直至循環(huán)結(jié)束；

步驟8 算法結(jié)束。

3 仿真實驗

首先，在NS2中建立如圖1所示的網(wǎng)絡(luò)拓?fù)鋱D，其參數(shù)設(shè)為：各鏈路容量為15Mbps，延時10ms，各節(jié)點(diǎn)緩存大小為1000packets，數(shù)據(jù)包均為1000Byte。同時，令W＝500，p1＝0.05，p2＝0.8，t0＝1。本文將提出的SAICSA算法與基于免疫規(guī)劃的模擬退火算法［12］（simulated annealing algorithm based on immune programming，SAIP）、遺傳模擬退火算法［13］（genetic simulated annealing algorithm，GSA）進(jìn)行比較分析。圖2中顯示了隨著失效邊數(shù)增加，3種算法的網(wǎng)絡(luò)生存性變化情況。從圖2中可以看出，當(dāng)失效邊數(shù)比較少時，3種算法的網(wǎng)絡(luò)生存性比較接近，而當(dāng)失效邊數(shù)比較多時，本文提出的SAICSA算法性能較優(yōu)，而GSA算法性能最差。進(jìn)一步分析其數(shù)據(jù)，SAICSA算法較SAIP算法和GSA算法的性能提高了8.76%和11.21%。

圖2 3種算法的網(wǎng)絡(luò)生存性比較

其次，將圖1中所示網(wǎng)絡(luò)鏈路ecd和egh移除后，研究這三種算法網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f（k）的變化情況。為了清楚觀察到結(jié)果的平穩(wěn)性，這里總共進(jìn)行了3000s仿真實驗，取中間1000的仿真結(jié)果進(jìn)行分析，如圖3所示。從圖3可以看出，總體上SAICSA算法所獲得的剩余數(shù)據(jù)傳輸量較大，說明該算法在鏈路失效的情況下能夠發(fā)揮較大的傳輸效率。而其余兩種算法來看，SAIP算法比GSA算法的性能稍優(yōu)。

為了進(jìn)一步研究SAICSA算法的生存性，這里將變異概率p1和交叉概率p2做深入分析。先將交叉概率p2恒定不變，p2仍取為0.8。在圖4中顯示了不同變異概率p1下，網(wǎng)絡(luò)生存性隨失效邊數(shù)的變化情況。從圖4可以看出，在失效邊數(shù)比較小的情況下，變異概率p1越大對應(yīng)的網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量越大，其親和度較大，變異的子抗體也就更容易被接受，那么網(wǎng)絡(luò)的生存性則越大；而當(dāng)失效邊數(shù)比較大的情況下，變異概率p1越小，對應(yīng)的網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量越大，變異子抗體反而容易被接受。

同時，將變異概率p1恒定不變，p1取為0.05。在圖5中顯示了不同交叉概率p2下，網(wǎng)絡(luò)生存性隨著失效邊數(shù)的變化情況。從圖5可以看出，在失效邊數(shù)比較小的情況下，交叉概率p2越大對應(yīng)的網(wǎng)絡(luò)生存性越大，而在失效邊數(shù)比較大時，情況發(fā)生的突變，交叉概率p2越小對應(yīng)的網(wǎng)絡(luò)生存性越大。由于失效邊數(shù)的增加導(dǎo)致網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量減小，必然會加大數(shù)據(jù)發(fā)送的沖突，此時交叉概率p2越小反而會減少沖突的發(fā)生，所以網(wǎng)絡(luò)生存性更高。

圖5 不同交叉概率的網(wǎng)絡(luò)生存性與失效邊數(shù)之間的關(guān)系

最后，討論SAICSA算法中初始溫度t0對網(wǎng)絡(luò)生存性的影響。令W＝500，p1＝0.05，p2＝0.8，當(dāng)t0分別取1、2、3時，1000s內(nèi)網(wǎng)絡(luò)生存性的仿真情況如圖6所示。從圖6來看，在仿真初期t0較大對應(yīng)的生存性越大，而在仿真后期t0較小對應(yīng)的生存性越大。這說明高溫對短期的網(wǎng)絡(luò)生存性提高起著更大作用，但是當(dāng)系統(tǒng)趨于平穩(wěn)時，低溫反而能夠提高網(wǎng)絡(luò)生存性。

圖6 不同初始溫度的網(wǎng)絡(luò)生存性比較

4 結(jié)束語

本文針對網(wǎng)絡(luò)生存性提出了一種新的刻畫方法，該方法首先根據(jù)網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸能力定義了網(wǎng)絡(luò)生存性指標(biāo)，并且通過免疫克隆模擬退火算法進(jìn)行克隆變異、交叉和選擇，使得變換后的抗體群保持了解的多樣性。同時，本文將提出的SAICSA算法與SAIP算法、GSA算法進(jìn)行仿真實驗，結(jié)果發(fā)現(xiàn)該算法具有較好的適應(yīng)性。在后續(xù)研究中，可結(jié)合魚群、蜂群等人工智能算法來對級聯(lián)失效下網(wǎng)絡(luò)的生存性進(jìn)行建模，以此形成比較完善的評價體系。

［1］Lin Y K.Reliability of a computer network in case capacity weight varying with arcs，nodes and types of commodity ［J］.Reliability Engineering and System Safety，2007，92 （5）：646－652.

［2］Gunawan I.Redundant paths and reliability bounds in gamma networks ［J］.Applied Mathematical Modeling，2008，32 （4）：588－594.

［3］WANG Jianwei，RONG Lili.Cascade－based attack vulnerability on the US power grid ［J］.Safety Science，2009，47 （10）：1332－1336.

［4］PAN Yantao，PENG Wei，LU Xicheng.Maximum flow based model and method of the maximum lifetime problem of sensor networks ［J］.Journal of National University of Defense Technology，2006，28 （3）：59－63 （in Chinese）.［潘晏濤，彭偉，盧錫城.求解傳感器網(wǎng)絡(luò)最大生存時間的最大流算法 ［J］.國防科技大學(xué)學(xué)報，2006，28 （3）：59－63.］

［5］LIU Aimin，LIU Youheng.Traffic performance analysis of network with unreliable components ［J］.Acta Electronica Sinica，2002，30（10）：1459－1462 （in Chinese）.［劉愛民，劉有恒.部件不可靠下的通信網(wǎng)業(yè)務(wù)性能分析 ［J］.電子學(xué)報，2002，30（10）：1459－1462.］

［6］HUANG Fuwei，RONG Peng，ZENG Lieguang.Approaches to quantitative analysis of survivability for SDH self－h(huán)ealing ring network ［J］.Acta Electronica Sinica，2001，29 （11）：1558－1560 （in Chinese）.［皇甫偉，容鵬，曾烈光.SDH自愈環(huán)生存性定量分析 ［J］.電子學(xué)報，2001，29 （11）：1558－1560.］

［7］LI Yun，ZHOU Xian，YOU Xiaohu，et al.IMECN：A new topology control algorithm for wireless sensor networks ［J］.Acta Electronica Sinica，2010，38 （1）：48－53 （in Chinese）. ［李云，周嫻，尤肖虎，等.IMECN：一種新的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?［J］.電子學(xué)報，2010，38 （1）：48－53.］

［8］Felemban E，Lee C G，Ekici E.MMSPEED：Multi－path multi－SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks ［J］.IEEE Transactions Mobile Computing，2006，5 （6）：738－754.

［9］TAN Yuejin，WU Jun，DENG Hongzhong.Evaluation method for node importance based on node contraction in complex networks［J］.Systems Engineering－Theory ＆Practice，2006，26（11）：79－83 （in Chinese）.［譚躍進(jìn)，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評估的節(jié)點(diǎn)收縮方法 ［J］.系統(tǒng)工程理論與實踐，2006，26 （11）：79－83.］

［10］XU Pengfei，MIAO Qiguang，LI Weisheng，et al.Adaptive simulated annealing algorithm and tabu search algorithm based on the function complexity ［J］.Acta Electronica Sinica，2011，39 （8）：1811－1817 （in Chinese）.［許鵬飛，苗啟廣，李偉生，等.基于函數(shù)復(fù)雜度的自適應(yīng)模擬退火和禁忌搜索新算法 ［J］.電子學(xué)報，2011，39 （8）：1811－1817.］

［11］WU Shaoxing，ZHANG Geling，MA Yujun.P2Prouting algorithm based on immune clonal annealing algorithm ［J］.Computer Engineering，2009，35 （18）：198－199 （in Chinese）.［吳紹興，張歌凌，馬玉軍.基于免疫克隆退火算法的P2P路由算法 ［J］.計算機(jī)工程，2009，35 （18）：198－199.］

［12］LU Lirong，XING Xiaoshuai，HUO Bingpeng.Simulated annealing algorithm based on immune programming ［J］.Computer Engineering，2007，33 （19）：196－198 （in Chinese）.［盧莉蓉，行小帥，霍冰鵬.基于免疫規(guī)劃的模擬退火算法［J］.計算機(jī)工程，2007，33 （19）：196－198.］

［13］LIU Jinming，WANG Xinsheng，LIANG Qingmei.Algorithm of QoS multicast routing based on genetic simulated annealing algorithm ［J］.Computer Engineering，2007，33 （9）：212－215（in Chinese）.［劉金明，王新生，梁清梅.基于遺傳模擬退火算法的QoS組播路由算法 ［J］.計算機(jī)工程，2007，33（9）：212－215.］