基于人工免疫算法的網(wǎng)絡(luò)可生存性增強與優(yōu)化

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

中國人民解放軍73698部隊

基于人工免疫算法的網(wǎng)絡(luò)可生存性增強與優(yōu)化

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

中國人民解放軍73698部隊

借助基于生物免疫系統(tǒng)的人工免疫算法能夠?qū)W(wǎng)絡(luò)進行自主的故障診斷和入侵檢測從而提高網(wǎng)絡(luò)的可生存性。在分析網(wǎng)絡(luò)可生存性基本原理的基礎(chǔ)上，結(jié)合人工免疫算法的思想提出了一種增強網(wǎng)絡(luò)可生存性的方案。

網(wǎng)絡(luò)可生存性；故障診斷；人工免疫算法；AIA

1 基于人工免疫算法的網(wǎng)絡(luò)可生存性增強算法

1.1 算法整體描述

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

1.2 定義鏈路權(quán)值

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

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

定義：當網(wǎng)絡(luò)狀態(tài)為Si，網(wǎng)絡(luò)流量矩陣為Δ×D（其中1/w≤Δ≤w）時所有的鏈路費用和為：

1.3 利用人工免疫算法求解

（1）編碼

根據(jù)OSPF的編碼方案，將權(quán)值優(yōu)化求解問題的解表示為離散空間[1，65535]E內(nèi)的一個點。用wi來表示每條鏈路的權(quán)值。

（2）初始化

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

（3）評價函數(shù)

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

（4）抗體克隆與超變異

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

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

（5）抗體的濃度改變

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

2 實驗及結(jié)果分析

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

3 結(jié)論

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

[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]羅印升，李人厚，張雷等.人工免疫算法在函數(shù)優(yōu)化中的應(yīng)用.西安交通大學(xué)學(xué)報，2003，7(8):840-843

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

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

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

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

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

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