基于人工免疫算法的網絡可生存性增強與優化

朱靈靈，袁唐杰，孔鑫云，陸海維，鄭 劍，戴海波

中國人民解放軍73698部隊

基于人工免疫算法的網絡可生存性增強與優化

朱靈靈，袁唐杰，孔鑫云，陸海維，鄭 劍，戴海波

中國人民解放軍73698部隊

借助基于生物免疫系統的人工免疫算法能夠對網絡進行自主的故障診斷和入侵檢測從而提高網絡的可生存性。在分析網絡可生存性基本原理的基礎上，結合人工免疫算法的思想提出了一種增強網絡可生存性的方案。

網絡可生存性；故障診斷；人工免疫算法；AIA

1 基于人工免疫算法的網絡可生存性增強算法

1.1 算法整體描述

本文采用Perelson與Oster所提出的形態空間模型(Shape-Space)來對免疫細胞與抗原間的相互作用進行定量的描述，把抗原和抗體分別表示為：在P維的形態空間SP內，抗體和抗原分別用P個歸一化的變量進行描述，而網絡的故障狀態共有P個不同的特征值，抗體為Ab={x1,x2,…，xp}，抗原為Ag={y1,y2,…，yp}。抗體與抗原的集合表示為AB={Abi|i=1,2,…，N}，AG={Agi|i=1,2,…,M}，式中M、N分別表示抗原和抗體的個數，xi和yi分別表示抗體Ab和抗原Ag的基因。算法中將直接進行個體基因的變異等操作。

1.2 定義鏈路權值

將各鏈路的權值是從1到65535之間的某個整數，用來表示使用該鏈路來傳輸數據包所消耗的代價。由于對給定的一個網絡，其鏈路權值的分配情況決定節點之間的路由，因此算法就是在滿足一定流量波動的范圍內及可能會出現鏈路故障的情況下，尋找能夠使網絡擁塞發生的可能性最小的一種權值的分配方案。

根據鏈路狀態協議OSPF，源節點到目的節點間(s,t)的流量路由到在(s,t)之間的最短路徑上，最短路徑根據鏈路權值確定。所以可將權值分配的問題概括為：確定一種權值分配策略W=(w1, w2,…,w||E)來求得使所有鏈路費用的和最小的目標函數。

定義：當網絡狀態為Si，網絡流量矩陣為Δ×D（其中1/w≤Δ≤w）時所有的鏈路費用和為：

1.3 利用人工免疫算法求解

（1）編碼

根據OSPF的編碼方案，將權值優化求解問題的解表示為離散空間[1，65535]E內的一個點。用wi來表示每條鏈路的權值。

（2）初始化

初始化抗體數量在解空間[1，65535]E隨機選擇。

（3）評價函數

評價函數根據φe的定義函數來確定。當網絡的拓撲與流量矩陣都確定的情況下，某個給定的權值的分配方案就可以決定路由的最短路徑樹，從而可以決定整個網絡中流量的分布；然后再通過統計每條鏈路的流量就能夠得到鏈路的實際利用率，從而最終得到全網的費用總和。

（4）抗體克隆與超變異

為保證抗體的多樣性并且提高記憶抗體生成的速度，本文引入抗體的克隆選擇與超變異思想。克隆選擇是只對那些能識別抗原的抗體細胞(表現為和抗原間的親和力超過某一規定的閾值）進行復制，并且通過免疫系統的選擇和保存，那些無法識別抗原的機體細胞不被選擇，并且不復制。

因為最終要得到能夠表示抗原的結構的記憶抗體的集合但并不是來找一個最優解，因此為避免產生的抗體間的相似性，本文擴大了記憶抗體表示的范圍，將克隆數量設置為1，這表明和抗原親和力最高的抗體只進行一個復制，同時根據下式進行超變異：=-α(-A)。式中表示變異后的新抗體，表gi示變異前的原抗體，參數α稱作成熟率或學習率，其大小根據親和力的大小設定，一般親和力越大，α的值設置的就越小，本文將α設置為抗原和抗體間的歐氏距離α=‖Agi-‖。本文的超變異過程是一個偏向進化過程，通過Ag-Ab的互補和α成比例的增長，因此，為抗原的識別能力進行循環改進，通過引導來使搜索朝著局部優化的方向發展（貪婪搜索）。

（5）抗體的濃度改變

因為免疫系統中一種抗體在受到抗原的刺激或者其它抗體的刺激抑或是抑制時，此類抗體數量將會發生改變。親和力較大抗體的濃度會提高，而當升高到某值時則會被抑制，隨之濃度較低抗體產生和選擇的概率則會增大。假設在抗體集合中個體的個數為N，則抗體Abv濃度按下式計算

2 實驗及結果分析

實驗場景設置：對于無故障的場景，節點i，j之間流量在0.5dij到2dij(w=2)的范圍波動，其中dij為節點i、j之間的流量；根據節點之間的最短路徑來求出節點i與j之間的每條鏈路的流量，由此迭代進行從而最終得到每條鏈路的總流量，進而可以得到每條鏈路的鏈路利用率。針對鏈路發生故障的場景，首先，分別考察各個鏈路出現故障的情況，然后根據新的拓撲結構重新進行路由計算，最后求出每條鏈路的利用率。

3 結論

網絡的可生存性要求大規模網絡系統在遭遇到攻擊或者故障時，能及時地通過自我適應和重新配置與進化而恢復或者維持關鍵任務。本文首先闡述了網絡可生存性和人工免疫算法的理論，然后提出了基于人工免疫算法的網路可生存性增強方案，采用形態空間模型來對免疫細胞與抗原間的相互作用進行定量的描述，通過抗體克隆及超變異等方法由初始抗體集合，通過權值矩陣設置來優化網絡，提高網絡的生存性。仿真結果表明，所設計的方案具有可行性和實用價值。

[1]Howard F.Lipson,David A.Fisher.Survivability-A New Technical and Business Perspective on Security.Proceedings of the New Security Paradigms Workshop,1999.

[2]Nancy R.Mead,Robert J.Ellison.Survivable Network Analysis Method.http://www.cert.org/archive/pdf/00tr013.pdf,2000

[3]羅印升，李人厚，張雷等.人工免疫算法在函數優化中的應用.西安交通大學學報，2003，7(8):840-843

袁唐杰（1992-），四川成都人，助理工程師；

孔鑫云（1988-），江蘇常州人，助理工程師；

陸海維（1991-），江蘇鹽城人，助理工程師；

鄭劍（1988-），福建莆田人，助理工程師；

戴海波（1987-），湖南岳陽人，助理工程師。

朱靈靈（1991-），安徽黃山人，助理工程師；