基于NNVD的网络化软件多步控制算法研究

马迎辉+彭成+张文佳+薛志山+满君丰

摘  要：网络化软件系统规模的增大不仅增加了理解和优化系统的难度，而且一个小的异常就有可能引发整个系统的崩溃。因此，针对网络化软件系统的异常行为，本文提出了一种基于NNVD（network node value degree）的网络化软件多步控制算法，该算法从节点路径长度范围的角度去研究异常行为传播的局域控制，通过网络化软件节点的重要程度选择控制节点，分析了在无标度网络软件系统中进行局域多步控制的有效性。研究表明，该算法能够在一定程度上抑制异常行为的传播，使异常能够在一定的范围内得到有效的控制。

关键词：网络化软件;软件异常行为;多步控制算法

中图分类号：TP301.6 文献标识码：A

The Network Software Multistep Control Algorithm Based on NNVD Research

MA Ying-hui， PENG Cheng， ZHANG Wen-jia， XUE Zhi-shan， MAN Jun-feng，

（College of Computer and Communication， Hunan University of Technology， Zhuzhou， Hunan 412000，China）

Abstract： The increasing scale of networked software system not only increases the difficulty to understand and optimize the system， but a small anomaly is likely to cause the collapse of the whole system. Therefore， in view of the abnormal behavior of networked software system， this paper proposed a networked software based on NNVD multistep control algorithm， the algorithm from the perspective of the node path length range to study the spread of the abnormal behavior of local control， through the network selection to the importance of the control software node， in a scale-free network software system are analyzed in local multistep control effectiveness. Studies show that the proposed algorithm can restrain the spread of abnormal behavior to a certain extent， make exceptions can get effective control in a certain scope.

Key words： networked software; software abnormal behavior; Multi-step control algorithm

1  引言

随着Internet的发展以及计算机Internet网络和自动控制技术在经济、社会和国防等领域的信息化应用，软件系统呈现出两个转变：（1）软件运行平台从集中、封闭单机环境向开放、动态和多变网络环境转变;（2）软件系统的功能向各种应用领域和为大众用户提供综合服务转变。这使得软件系统呈现出网络化的新特征，软件的规模和复杂性剧增。对于网络化软件而言，我们面对的不单单是像Internet这样的单个网络和系统，而是一个系统的系统。由群体用户行为驱动的各层元素间的错综复杂的联系和交互，构成了一个庞大而又复杂的网，确切地说是一个动态变化的多尺度网络的网络，而且其中的节点（既可以是路由器、网页、web服务，也可以是用户或者agent）和边的含义不尽相同。因此，网络化软件系统中的任何节点发生故障，都有可能引发多米诺效应，最终导致系统崩溃[1]。据此，研究网络化软件局域范围内的多步控制方法刻不容缓，以期在系统崩溃之前对其进行多步控制，维持系统稳定正常的运行。

目前，复杂网络中的三种典型的免疫控制算法包括random immunization（随机免疫）策略[2]、targeted immunization（目标免疫）策略[3]和acquaintance immunization（熟人免疫）策略[4]。随机免疫指为了预防控制病毒的扩散，随机地选择网络中的部分节点并对其进行免疫，此种策略没有考虑网络节点间的差异性，网络中的所有节点被同等看待，节点被选中的概率是相同的。但是在无标度网络中采用随机免疫策略需要对网络中几乎所有的节点进行免疫，这在现实的复杂网络中，几乎是不可能的。目标免疫是依据无标度网络中度分布的不均匀性，顺序地选择部分度大的节点并对其进行免疫。一旦这些度大的节点被免疫，那么与它们连接的边则从网络中剔除，很大程度上减少了病毒传播的途径。但是这种策略需要事先了解网络的拓扑和网络中节点的度。因此，对于一些规模较大的动态网络来说也是不现实的。Cohen等人提出的熟人免疫属于一种局域控制策略，它不需要知道网络的拓扑结构和全局信息，其目的在于找出度数大的节点进行免疫。

鉴于此，本文提出了一种基于NNVD（network node value degree）的网络化软件局部控制免疫算法。该算法从异常源点出发，然后对异常源点周围的各邻居节点的重要程度进行计算，选出重要度大的节点依次进行免疫。在异常源点周围一定的距离范围内对异常源点进行局域控制，从而控制异常行为在网络化软件系统中的蔓延。最后，通过仿真实验对本文的算法进行认证，证明了该算法的准确性和有效性，为后续的工作提供了理论基础。

2  相关工作

近年来，国内外学者都以已有的ER随机网络（Random network）[5]、WS小世界网络（Small world network）[6]和BA无标度网络（Scale-free network）[7]等复杂网络模型为依托来研究病毒传播的规律。随后，一些经典的传播模型也被相继提出，比较经典的有SI模型[8]、SIS模型[9]、SIR模型[10]等。在复杂的网络系统中，为了更好的理解网络结构与网络性能之间的关系，复杂网络方面的控制成了近年来研究的热点。Wang和Chen等[11]作了初步尝试，将控制策略首次应用到无标度复杂混沌动态网络中，由于BA网络结构具有非均匀行的特征，因此可以通过对网络中少数节点进行控制，最终达到网络结构稳定性的目的。随后，Li等[12]在复杂动态网络牵制控制方面，使用状态反馈控制使系统达到平衡状态，并且可以在不同的网络耦合强度下验证得到的是系统渐进稳定的充分条件。Liu等[13]利用局部反馈控制给出连续离散时间的复杂网络牵制控制结论。虽然以上这些关于控制方面的研究取得了很好的进展，但是这些研究都是集中在复杂网络系统方面，在网络化软件方面确鲜有涉及。

3  网络化软件多步控制算法

3.1相关定义

定义1（SIR模型）网络化软件系统里的节点分为三类：健康节点（S）、感染节点（I，隐含错误节点，如内存溢出等）和免疫节点（R）。在异常行为传播初期，软件系统中某些健康节点受到异常节点感染，并通过一定的概率将异常传播到其邻居节点。一旦S类节点被感染，则成为I类节点。这些I类节点又会变成新的感染源去感染其它节点。R类节点为免疫节点，是已经恢复为健康节点并且获得免疫能力的节点，在网络化软件系统里表现为不能被感染并且也不能感染其邻居节点。

定义2（异常节点间故障传播概率）异常节点间的故障传播概率e（m，n）定义为：

当扩散比率小于某一阈值δ时，异常源点的扩散对系统几乎没有影响，则免疫停止。

4  实验及分析

为了验证本文算法的有效性，需要进行相关的实验分析。本文使用MATLAB仿真软件分析了本文算法的有效性。

由于网络化软件具有较为复杂的网络特性，本文只考虑网络化软件的无标度网络特性。又因为无标度网络的幂率参数与网络结构和性能特征具有较强的关联性，本文实验取=2-3.5作为网络结构参数。本文算法的免疫节点选择方法，在确保免疫节点定位精度的前提下，极大降低了网络的能量消耗，并且构建了网络免疫节点的最佳路径。本文算法免疫效果的仿真结果如图1所示：

图1   从节点的能耗量方面考虑的免疫效果图

稳态感染率以及故障传播速度是评估网络免疫效果的指标。因此本文在模型网络以及实际网络中进行了仿真分析，用图2描述。采用SIR模型，感染率v=0.03，回复率=0.01，只考虑网络化软件的无标度网络特性，N=1000，L=4000。仿真结果取50次的平均值。

图2   无尺度网络中免疫度

为了进一步分析本文算法的免疫效果，实验对本文算法进行了多次的仿真分析，获取的平均统计结果如图3所示。结果参数对本文算法有一定的影响，这是由无尺度网络的特性决定的，越大，本文算法的免疫效果越好。

图3 算法的解析值与仿真值比较

5  结束语

研究网络化软件异常行为的多步控制算法，对提高这种新型软件系统的稳定性和可靠性起重要作用。本文提出了一种基于网络节点重要程度的多步控制算法，并给出了详细的定义和计算方法。实验结果表明，该算法能够准确获取网路化软件系统中的免疫节点，达到控制异常行为传播的目的。本算法的创新之处在于其填补了网络化软件在异常行为控制方面的空白，但是相对于复杂网络中的一些免疫算法，在算法性能方面仍有很多不足之处。因此，如何改进并且提高算法的性能是我们下一步亟待需要解决的问题。

参考文献：

[1] 马于涛，何克清，李兵，刘婧.网络化软件的复杂网络特征实证[J].软件学报，2011，22（3）：381-407.

[2] Yu L， Xue H，Gao X，et al.Epidemic spread model based on cellular automata[J].Computer Engineering and Aplications，2007，43（2）：196-237

[3] Gomez-Gardenes J， Echenique P， Moreno Y. Immunization of real complex communication networks[J].European Physical Journal B，2006，49（2）：259-264

[4] Gallos L K， Liljeros F， Argyrakis P， et al. Improving immunization strategies[J].Physical Review E（Statistical， Nonlinear， and Soft Matter Physics），2007，75（4）：45104-1

[5] Eedǒs P， Rényi A. On the evolution of random graphs[J].Publ. Math. Inst. Hung. Acad. Sci， 1960， 5： 17～61.

[6] D.J. Watts， S. H. Strogatz. Collection dynamics of small-world networks[J]. Nature， 1998，393（6684）：440-442.

[7] A.-L. Barabási， R. Albert. Emergence of scaling in random networks[J].Science，1999，286（5439）：509-512.

[8] Pastor-Satorras， R， Vespignani， A. Epidemic Spreading in Scale-free Networks[J].Physical Review Letters， 2001， 86（14）：3200-3203.

[9] Eguiluz V M， Klemm， K.. Epidemic Threshold in Structured Scale-Free Netwoks[J]. Physical Review Letters， 2002，89（10）：108701.

[10] Moore C， Newman， M E J. Epidemics and Percolation in Small-world Network [J]. Physical Review E， 2000， 61（5）：5678-5682.

[11] Wang X F， Chen G. Pinning control of scale-free dynamical networks. Physica A， 2002，310 （3-4）：521-531.

[12] Li X， Wang X F， Chen G. Pinning a complex dynamical networks to its equilibrium. IEEE International Symposium on Circuit System-I，2004，51（10）：2074-2087.

[13] Liu Z X， Chen Z Q， et al. Pinning control of weighted general complex dynamical networks with time delay. Physica A，2007，375（1）：345-354.

[14] 彭成，杨路明，满君丰.网络化软件异常行为传播研究[j].电子学报，2013，41（10）：2074-2081

[15] 彭成，杨路明，满君丰.网络化软件交互行为动态建模[J].电子学报，2013，41（2）：314-320