基于小波变换和鱼群算法的网络抗毁性研究

段谟意

（南京铁道职业技术学院 软件学院，江苏 南京210031）

0 引 言

随着无线传感器网络的快速发展，网络抗毁性的重大理论意义和应用价值也日益凸显。网络抗毁性描述了网络在遭受意外故障或蓄意攻击时的可靠性，其节点和链路的性能对网络的抗毁性产生非常重要作用。当网络中某个热点节点的能量耗尽时，该节点的失效使得网络被分割，从而导致性能快速下降。同时，由于节点负荷的加重，容易导致拥塞和分组丢失，造成链路中断。所以，如何避免热点节点成为无线传感器网络抗毁性能的瓶颈，国内外学者对此做了大量研究。郭虹等［1］针对无线网络节点的重要度，利用结构熵定义了网络抗毁熵、节点抗毁度和全网抗毁度，并通过仿真分析了所定义的测度是移动无线网络抗毁性评估的有效指标。黎放等［2］在网络总容量不变、容许参数可变的基础上，构建了资源有限的级联失效模型，并建立了四种典型的容量分配策略，但是存在度偏好容量分配策略不如负荷偏好策略，以及平均容量分配策略效果不好等问题。文献 ［3］提出了基于局部负荷分配策略的级联失效模型，并且发现在某些条件下攻击低度节点对网络的破坏程度反而大于高度的节点。文献 ［4］的研究说明了当高度节点获得更多的容量分配时，能够有效提高网络抵抗级联失效的能力。文献 ［5］利用凝聚度及生成树宏观评估全连通网络的相对抗毁性，但缺乏对非连通网络节点重要性的有效计算。文献 ［6］基于通信网络抗毁性的定义，采用多抗毁性度量值的评估技术，对通信网络的抗毁性进行评价，并构建了抗毁性模型。文献 ［7－8］针对网络部件失效情况采用概率加权法，深入研究了满足业务要求的状态概率求和。

针对上述问题，本文在以往定义的网络节点抗毁性基础上，首先采用小波变换减少业务流的相关性，并且通过鱼群算法来刻画业务流状态。同时，利用仿真实验深入研究了该方法的有效性。

1 抗毁性定义

假设存在如图1所示的无线传感器网络G （V，E，F），其中，V表示点集，E表示边集，F表示两节点间的流量。令D＝ （dij）表示节点Vi和Vj的最短路径的边数，并且假设某边ek上对应的权重为 （k，fij表示节点Vi和Vj之间的流量。

图1 网络拓扑结构

作者曾提出节点Vi关于路径 （Vi，Vj）的重要度定义

式中：m——路径 （Vi，Vj）上存在的节点数。在网络遭受攻击时，随着平均路径长度dij的增加，μi不断增大，当网络的连通性遭到破坏时dij＝0，μi＝0。

同时，定义了节点Vi的抗毁性指标

式中：B——节点初始能量，b——节点剩余能量，c1和c2——能量因子和流量因子，且c1＋c2＝1。

从式 （1）和 （2）可知，节点抗毁性主要受到的节点能量与节点流量影响，而节点能量与自身环境有着重要关联，所以这里针对节点流量进行详细研究。此前作者曾基于元胞蚁群算法提出过一种计算方法ICA （invulnerability based on cellular ant），其思路是通过定义元胞移动规则来改进蚁群算法，以此评价节点抗毁性。对此，本文提出另外一 种 计 算 方 法 IWA （invulnerability based on wavelet transform and fish swarm algorithm），采用小波变换和鱼群算法来研究节点抗毁性。

2 数学模型

2.1 鱼群行为定义

这里将业务流看作鱼群［9－10］，节点重要度看作食物浓度，其流量作为状态指标，以下给出四种鱼群行为定义。

（1）觅食行为

觅食行为是鱼群生存的基本行为，鱼群通过感官向食物浓度大的地方移动。假设鱼群当前状态为fi，在其邻域内随机选择另外一个状态fj，根据式 （3）将鱼群置于区域中心ri

式中：xi和yi——搜索区域位置，该k为鱼群数量。由式（1）计算当前的食物浓度ui和uj。如果ui＜uj，则该鱼群朝此方向移动一步，令ui＝ui＋1，并将fj作为当前状态，否则停止不动。直到试探多次后仍未移动，则考虑采取其它行为。

（2）聚群行为

在聚群移动的过程中需要同时保证鱼群周围的食物浓度和鱼群间距离。假设鱼群当前状态为fi，对应的食物浓度为ui，并且该区域内的鱼群数量为ni，总的鱼群数量为n，umin表示食物浓度的最小阈值，（min用于衡量鱼群间最小距离。定义

1）如果ui＜umin，并且 （i≥ （min，说明该区域内鱼群有足够距离，但是食物浓度不高，则执行觅食行为；

2）如果ui≥umin，并且λi＜λmin，说明该区域内食物浓度足够，但是存在过多鱼群，鱼群间隔空间不够，则朝着该区域中心反方向执行随机行为；

3）如果ui≥umin，并且λi≥λmin，则该区域内的食物浓度和鱼群间距离，鱼群将向该区域中心位置ri移动一步，令ui＝ui＋1，并更新当前状态。

（3）追尾行为

当鱼群中的个体寻到食物，其它个体会尾随其后，朝着距自身最优的个体靠拢。假设鱼群当前状态为fi，在邻域ri内存在最优个体fk，如果ui＜uk，并且保证λi≥λmin，则说明该区域内保证了足够的食物浓度和鱼群间距，则朝fk方向移动一步，令ui＝ui＋1，并更新当前状态。否则执行觅食行为。

（4）随机行为

随机行为是从当前状态fi转移到另一可行状态fj。在求解过程中，当长时间没有获得最优解时，可考虑加入随机概率，使鱼群移动到邻域来搜索可行解。令鱼群的随机移动概率为

其中，△fij＝fi－fj，0≤θ≤1。

2.2 算法设计

考虑到实际业务流具有的分形特性［11－12］，首先利用小波变换［13］来平滑业务流，使网络节点有能力处理突发数据。然后根据定义的鱼群行为，对网络的抗毁性进行求解。具体算法如下所述：

（1）在开始时刻t，初始化各网络节点参数，同时设置鱼群相关信息；

（2）收集当前网络节点Vi的业务流状态，利用结合式（6）对业务流进行小波变换，以平滑突发情况

式中：j——小波分解层次，k——每一层的小波系数，Dj，k——小波系数，Aj，k——近似系数；

（3）将小波变换之后的业务流看作鱼群个体，根据式（1）计算其食物浓度ui；

（4）对鱼群执行定义的四种行为，获取最优值OPT；

（5）令i＝i＋1，并判断当前循环是否结束，或者最优值OPT已经连续有多次未变 （这里假设为8次），则结束寻优操作，跳转到步骤 （6），否则跳转到步骤 （2）；

（6）根据当前最优值OPT，结合式 （2）计算网络节点Vi的抗毁系数ki；

（7）令t＝t＋1，跳转到步骤 （1），直至最后时刻；

（8）算法结束。

3 仿真实验

首先，在OPNET中建立如图1所示的网络仿真图，各参数设定为：链路容量为10Mbps，延时10ms，各节点缓存大小为500packets，数据包大小为200Byte。并且采用分形高斯噪声FGN模型来产生分形业务流，令各节点发送业务流的速率为2000kbit／s，其相关程度指标H＝0.9。这里针对的路径为 （Va，Vk），需要计算的是节点k的抗毁性。将IWA算法与ICA算法获得的抗毁性进行比较，如图2所示。在10s内，IWA的抗毁性整体要高于ICA。经过数据统计，IWA较ICA的性能提高了6.41%。

图2 IWA算法与ICA算法的抗毁性比较

其次，为了更清楚比较两种算法的性能，这里依次减少路径 （Va，Vk）上的连接边数，观察节点k抗毁性的变化情况，结果如图3所示。整体趋势上，随着失效边的增多，两种算法的抗毁性随之减小。这是因为减少了连接边相当于降低了节点之间的连通度，使得网络抵抗破坏的能力降低。但是IWA比ICA降低的速度较慢，这说明在同等情况下，IWA抵抗破坏的能力更强。并且，在图4中显示了节点k的抗毁性与失效节点之间的关系。从整体趋势上说，图4和图3有着类似情况，随着失效节点的增多，节点k的抗毁性减小。在失效节点数比较少时，IWA比ICA降低的速度较慢，但是失效节点在达到4之后，IWA和ICA对应的抗毁性比较接近。

进一步地，为了研究IWA算法的性能，在图5中显示了不同流量因子c2下，节点k的抗毁性与节点负载之间的关系。整体趋势上来说，随着负载的增加，节点k的抗毁性先呈上升趋势，达到极大值点后又呈现出下降趋势。在抗毁性达到极大值点前，当负载小于800bit时，c2对应的值越小反而其抗毁性越大，而负载介于800－1200bit时，情况发生了突变，c2对应的值越小其抗毁性越小。当抗毁性超过极大值点后，整个情况正好与之前状态相反。

图5 抗毁性与节点负载 （bit／s）之间的关系

同时，这里将长相关参数H作为应变量，图6显示了不同流量因子c2下节点k抗毁性的变化情况。从图6可以看出，随着H值的增加抗毁性是随之增加的。当H值较小时，c2对应的值越小其抗毁性越大，当H值超过0.7－08区域时，c2对应的值越大其抗毁性越大。这里存在突变情况，分析其原因是由于有限带宽产生的作用。

图6 抗毁性与H之间的关系

4 结束语

本文基于小波变换和鱼群算法提出了一种新的网络节点抗毁性评价方法IWA。该方法首先针对作者以往定义的网络节点抗毁性指标，采用鱼群算法来刻画业务流的性能状态。同时针对业务流的突发，利用小波变换来减少其相关性。并且通过仿真实验，对比研究了与ICA评价方法的优劣，说明了IWA方法具有一定的适应性。在后续研究中，可考虑结合网络有效性和生存性进行动态关联建模，以此形成比较完善的评价体系。

［1］GUO Hong，LAN Julong，LIU Luokun.Research of metrics of Ad Hoc networks invulnerability considering node importance assessment ［J］.Journal of Chinese Computer Systems，2010，31 （6）：1063－1066 （in Chinese）. ［郭虹，兰巨龙，刘洛琨.考虑节点重要度的Ad Hoc网络抗毁性测度研究 ［J］.小型微型计算机系统，2010，31 （6）：1063－1066.］

［2］LI Fang，HU Bin，DI Peng.Optimization of dynamic invulnerability of scale free networks based on limited resource model［J］.System Engineering and Electronics，2012，34 （1）：175－178（in Chinese）.［黎放，胡斌，狄鹏.基于资源有限模型的无标度网络动态抗毁性优化 ［J］.系统工程与电子技术，2012，34 （1）：175－178.］

［3］WANG Jianwei，RONG Lili.Cascade－based attack vulnerability on the US power grid［J］.Safety Science，2009，47 （10）：1332－1336.

［4］LI P，WANG B H，SUN H，et al.A limited resource model of fault－tolerant capability against cascading failure of complex network［J］.The European Physical Journal B，2008，62 （1）：101－104.

［5］RAO Yuping，LIN Jingyu，ZHOU Dongfang.Method for network invulnerability and node importance evaluation ［J］.Computer Engineering，2009，35 （6）：14－16 （in Chinese）.［饶育萍，林竞羽，周东方.网络抗毁度和节点重要性评价方法［J］.计算机工程，2009，35 （6）：14－16.］

［6］REN Junliang，SHEN Maoxing，SHI Xiangfeng.A method of evaluating the invulnerability of communication networks structure ［J］.Journal of Air Force Engineering University （Natural Science Edition），2010，11 （1）：70－73 （in Chinese）. ［任俊亮，申卯兴，史向峰.通信网络抗毁性的评价方法 ［J］.空军工程大学学报 （自然科学版），2010，11 （1）：70－73.］

［7］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.

［8］Gunawan I.Redundant paths and reliability bounds in gamma networks ［J］.Applied Mathematical Modeling，2008，32 （4）：588－594.

［9］DAI Shangping，JI Yinli，WANG Hua，et al.Extracting classification rules based on multi artificialfish swarm cooperation algorithm ［J］.Application Research of Computers，2012，29（5）：1676－1679 （in Chinese）. ［戴上平，姬盈利，王华，等.基于多群协同人工鱼群算法的分类规则提取算法 ［J］.计算机应用研究，2012，29 （5）：1676－1679.］

［10］SHEN Wei，GUO Xiaopen，WU Chao，et al.Forecasting stock indices using radial basis function neural networks optimized by artificial fish swarm algorithm ［J］.Knowledgebased Systems，2011，24 （3）：378－385.

［11］Masugi M.Multi－fractal analysis of IP－network traffic based on a hierarchical clustering approach ［J］.Communications in Nonlinear Science and Numerical Simulation，2007，12 （7）：1316－1325.

［12］XU Xiaodong，ZHU Shirui，SUN Yamin.Anomaly detection algorithm based on fractal characteristics of large－scale network traffic［J］.Journal on Communications，2009，30 （9）：43－53 （in Chinese）.［许晓东，朱士瑞，孙亚民.基于分形特性的宏观网络流量异常分析 ［J］.通信学报，2009，30 （9）：43－53.］

［13］BAI Xiangyu，YE Xinming，JIANG Hai.Network traffic predicting based on wavelet transform and autoregressive model［J］.Computer Science，2007，34 （7）：47－54 （in Chinese）.［白翔宇，叶新铭，蒋海.基于小波变换与自回归模型的网络流量预测 ［J］.计算机科学，2007，34 （7）：47－54.］