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

中國(guó)人民解放軍73698部隊(duì)

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

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

中國(guó)人民解放軍73698部隊(duì)

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

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

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

1.1 算法整體描述

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

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

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

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

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

1.3 利用人工免疫算法求解

（1）編碼

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

（2）初始化

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

（3）評(píng)價(jià)函數(shù)

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

（4）抗體克隆與超變異

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

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

（5）抗體的濃度改變

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

2 實(shí)驗(yàn)及結(jié)果分析

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

3 結(jié)論

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

[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é)報(bào)，2003，7(8):840-843

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

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

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

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

戴海波（1987-），湖南岳陽(yáng)人，助理工程師。

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