基于元胞蚁群算法的网络生存性研究

江宇波 赵攀

摘 要：针对通信网络因链路失效而产生的网络拥塞问题，基于元胞蚁群算法提出了一种新的网络生存性评价方法SACA（Survivability Algorithm based on Cellular Ant）。该方法首先给出了网络生存性定义，并且通过元胞蚁群算法设计了生存性算法流程，以此获得网络剩余数据传输量。同时，利用NS2和MATLAB进行仿真实验，结果表明，相比于其它算法，SACA算法具有出较好的适应性。

关键词：生存性；剩余能量；失效；元胞蚁群

中图分类号：G642 文献标识码：B 文章编号：1002-7661（2014）09-285-02

目前，如何提高网络安全性成为网络的研究重点和研究热点。网络生存性已经成为影响其性能的关键问题[1]。网络生存性主要是指网络在遭遇外部攻击或自身故障等异常情况下，仍然能够及时维持可接受的业务质量的能力。为了有效评价并解决这一问题，国内外学者开展大量研究工作。2000年，Albert等[2]首先研究了不同度分布下复杂网络的有效性。Paolo Crucitti等[3]利用度和介概念提出了关键节点和链路评估模型，并讨论了不同状态下的网络生存能力。但是这些优化思想并没有从网络模型和网络状态进行深入分析，所以对于从本质上解决网络抗毁性的作用有限。皇甫伟等[4]定义了网络生存性指标，并基于灾害条件对具有SDH自愈环拓扑结构的网络生存性进行了定量分析。包学才等[5]针对全连通网络定义了不相交路径抗毁性评估模型，研究了全连通网络节点间不相交路径数的比重，从而能够定量计算通信网络的抗毁性。Wang Jianwei等[6]提出了基于局部负荷分配策略的级联失效模型，并且发现在某些条件下攻击低度节点对网络的破坏程度反而大于高度的节点。

针对上述问题，本文首先给出了网络生存性定义，并且利用元胞蚁群算法来计算剩余数据传输量[7-8]，进而获得当前网络生存性。同时通过NS2和MATAB进行仿真实验，深入研究了影响该方法的关键因素。

1、网络生存性定义

假设存在网络G（V， W， F）中，V代表节点集合（V=[1， 2， …， n]），W代表链路权重集合，F表示网络中任意两点之间的流量集合，假设网络中各节点位置具有随机性，并且节点的性质相同（如数据转发能力，缓冲大小等），这里将各节点出现失效的情况归纳为对应链路出现失效，同时假设各链路出现失效的概率相等。令网络中存在n段链路，正常情况下整个网络数据传输量为f，有k条链路失效时网络剩余流量为f（k）。那么，网络生存性则可以定义为：

（1）

其中：

（2）

在上述定义中，关键在于求解网络剩余流量f（k）。本文结合元胞自动机和蚁群智能算法对f（k）进行研究，将定义的元胞演化规则替换变异和交叉操作，以达到快速收敛的目的，同时降低了算法的运算量。

2、元胞蚁群算法

元胞自动机是一种时间和空间离散、可扩散的、状态有限的多维系统，普遍应用于非线性科学领域。

本文采用Moore型元胞结构，如图1所示，在下一时刻蚂蚁按照概率p选择周围8个元胞和自身中的最优状态进行转移：

（3）

其中，ξ和ζ为非负常数，λi为蚂蚁i为中心r为半径的邻域内的单位面积内的节点分布，Δλ表示两相临邻域内的节点分布差，yi为每个蚂蚁对应的状态函数，Δyij=yi-yj，并且状态函数yi为定义为：

（4）

同时这里定义如下元胞演化规则：

（a） 选择任意一个元胞i，通过计算临域内各yi值，记录其中最优值yopt=yi。

（b） 在临域半径r内任意选取元胞i和j，并计算相应的yi和yj；如果yi

这里利用元胞蚁群给出上述数学模型的求解算法（Botnet Detecting algorithm based on Cellular Ant，BDCA）：

1、在开始时刻T，初始化网络拓扑结构，网络剩余数据传输量f（k）、元胞蚁群规模为M，并确定元胞蚁群的转移概率p和搜索区域半径r，最大迭代阈值MAX；

2、确定蚂蚁的搜索区域及搜索中心位置Oi：

（13）

其中，xmax和xmin为搜索区域上下边界，rand（）产生（0， 1）之间的随机数；

3、在Oi为中心、r为搜索半径的区域内，蚂蚁i搜索是否存在比当前状态函数yi更优的元胞；如果存在则按照概率p进行移动，如果移动成功，则丢弃当前中心区域Oi，重新计算当前蚂蚁i的目标函数值，以及当前最优解，同时更新方程修改轨迹强度；

4、重复上述步骤（3），完成所有蚂蚁的更新操作；

5、令T=T+1，跳转到步骤（2）继续执行，直至Δλ趋于0或者跌代次数超过阈值MAX时停止；

6、输出当前的最优解，即为稳定状态下最优的网络剩余数据传输量f（k）；

算法结束。

本文针对网络生存性提出了一种新的刻画方法SACA。该方法首先根据网络剩余数据传输能力给出了网络生存性指标，通过定义元胞演化规则并结合蚁群算法，将网络节点集合看作蚁群，使得在网络失效的情况下能够快速收敛，从而获得全局最优。最后，本文将提出的SACA算法与SAICSA 算法、ASATS算法进行仿真实验，结果发现该算法具有较好的适应性。同时在今后的研究中，可以考虑联系网络有效性和抗毁性进行动态建模，以此形成较为完善的评价体系结构。

参考文献：

[1] Lazarou G Y， Baca Julie， Frostv S， Evans J B. Describing network traffic using the index of variability[J]. IEEE /ACM Transactions on Networking， 2009， 17 （5）： 1672-1683.

[2] Albert R， Jeong H， Barabasi A L. Error and attack tolerance of complex networks [J]. Nature， 2000， 406： 378-382.

[3] Crucitti P， Latora V， Marchiori M， Rapisarda A. Error and attack tolerance of complex networks [J]. Physica A， 2004， 340（1）： 388-394.

[4] 皇甫伟， 容鹏， 曾烈光. SDH 自愈环生存性定量分析[J]. 电子学报， 2001， 29（11）： 1558-1560.

[5] 包学才， 戴伏生， 韩卫占. 基于拓扑的不相交路径抗毁性评估方法[J]. 系统工程与电子技术， 2012， 34（1）： 168-174.

[6] Wang Jianwei， Rong Lili. Cascade-based attack vulnerability on the US power grid[J]. Safety Science， 2009， 47（10）： 1332-1336.

[7] 曹春红，王利民，赵大哲. 基于离散元胞蚂蚁算法的几何约束求解技术研究[J].电子学报，2011，38（5）：1127.