基于免疫克隆模拟退火算法的网络生存性研究

段谟意

（南京铁道职业技术学院 软件学院，江苏 南京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.］