基于人工免疫算法的网络可生存性增强与优化

朱灵灵，袁唐杰，孔鑫云，陆海维，郑 剑，戴海波

中国人民解放军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-），安徽黄山人，助理工程师；