基于免疫克隆模擬退火算法的網絡生存性研究

段謨意

（南京鐵道職業技術學院 軟件學院，江蘇 南京210031）

0 引 言

網絡生存性作為網絡可靠性的重要衡量指標，它主要應用于隨機破壞作用下的網絡可靠性研究，包括受到攻擊后的網絡剩余通信能力以及損失程度。目前針對通信網絡的生存性討論是網絡可靠性領域的研究熱點［1－3］。對此，國內外學者進行了大量工作。文獻 ［4］針對網絡最大流建立了獲取傳感器網絡最大生存時間確切值的算法。文獻 ［5］通過綜合考慮通信網絡的業務量影響因素和連通性，提出了網絡可靠性評價測度。皇甫偉等［6］定義了網絡生存性指標，并基于災害條件對具有SDH自愈環拓撲結構的網絡生存性進行了定量分析。在保證網絡連通性的前提下，文獻［7］通過減少網絡節點的能量消耗來延長整個網絡的生存時間。文獻 ［8］通過綜合考慮同時滿足時延性和可靠性需求，重點分析了網絡層與MAC層對通信范圍的要求。文獻 ［9］通過采用節點刪除法比較了刪除節點前后的網絡性能變化，但存在網絡不連通和生存性計算不精確的缺陷。

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

1 網絡生存性定義

假設存在如圖1所示的通信網絡G （V，E，F），其中，V表示點集，E＝ （eij）表示邊集，F＝ （fij）表示網絡中任意兩點之間的流量，即fij表示節點Vi和Vj之間的流量。

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

圖1 網絡拓撲結構

那么，網絡的生存性則可定義為

在上述定義中，關鍵在于求解網絡剩余數據傳輸量f（k）。本文首先結合模擬退火算法［10］提出了如下評價網絡生存性算法：

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

步驟2 如果在f（k）的初始解xj的領域內存在新的可行解x′j，計算當前這兩個解的函數差 Δy，Δy＝y（x′j）－y （xj）；

步驟3 根據Metropolis準則，如果Δy＜0，則接受xj作為f （j）的當前最優解；

步驟5 執行退火操作，令tj＋1＝R＊tj，j＝j＋1；

步驟6 跳轉到步驟2，直至達到該溫度下的熱平衡狀態，輸出當前最優解作為網絡剩余數據傳輸量f（j）的最終解；

步驟7 根據式 （2）計算網絡的生存性s；

步驟8 算法結束。

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

2 SAICSA算法描述

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

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

步驟1 初始化網絡參數，確定抗體群A，以及種群規模W，變異概率p1，交叉概率p2，初始溫度t0等參數；

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

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

步驟3 根據式 （4）將第k個抗體進行克隆，得到規模為Wr的新抗體群B

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

步驟4 按照以下規則對新抗體群B進行克隆變異操作，產生臨時抗體群C：

（1）根據式 （5）計算產生父抗體b的子抗體b＇

其中，poisscdf（）為泊松分布函數；

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

步驟5 按照以下規則對抗體C進行克隆交叉操作，產生新的抗體群A＇；

（1）產生 ［0，1］內的泊松分布隨機數ε，如果ε＜p2，則按照式 （6）和式 （7）對父抗體b1和b2進行交叉操作獲得 子抗體b1＇和b2＇

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

步驟6 當tk＝0時，退火過程結束，跳轉到步驟8；

步驟7 否則，令k＝k＋1，tk＋1＝tk（1－k／B），跳轉到步驟2，直至循環結束；

步驟8 算法結束。

3 仿真實驗

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

圖2 3種算法的網絡生存性比較

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

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

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

圖5 不同交叉概率的網絡生存性與失效邊數之間的關系

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

圖6 不同初始溫度的網絡生存性比較

4 結束語

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

［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）.［潘晏濤，彭偉，盧錫城.求解傳感器網絡最大生存時間的最大流算法 ［J］.國防科技大學學報，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）.［劉愛民，劉有恒.部件不可靠下的通信網業務性能分析 ［J］.電子學報，2002，30（10）：1459－1462.］

［6］HUANG Fuwei，RONG Peng，ZENG Lieguang.Approaches to quantitative analysis of survivability for SDH self－healing ring network ［J］.Acta Electronica Sinica，2001，29 （11）：1558－1560 （in Chinese）.［皇甫偉，容鵬，曾烈光.SDH自愈環生存性定量分析 ［J］.電子學報，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：一種新的無線傳感器網絡拓撲控制算法 ［J］.電子學報，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］.系統工程理論與實踐，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）.［許鵬飛，苗啟廣，李偉生，等.基于函數復雜度的自適應模擬退火和禁忌搜索新算法 ［J］.電子學報，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］.計算機工程，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）.［盧莉蓉，行小帥，霍冰鵬.基于免疫規劃的模擬退火算法［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］.計算機工程，2007，33（9）：212－215.］