基于广度优先搜索算法的复杂网络可靠性分析

荆平 李永明 韦利春 高红慧

摘要：要加强网络的可靠性，需要对非叶子节点关联的割边进行多重连接，本文给出了利用广度优先搜索算法寻找非叶子节点关联的割边算法，对网络的割边进行加固。对加固后的网络进行了随机故障和故意攻击的测试，并给出了一些仿真结果。

关键词：复杂网络；Prim算法；割边；广度优先搜索算法；可靠性

1 引言

由于数据网络日趋复杂、网络规模日趋庞大,客观、可靠地对网络进行规划设计显得愈发重要。因此,在没有实际的路由实验环境下,一种有效的手段就是利用网络仿真技术建立仿真平台进行仿真实验。网络仿真中最重要的前提步骤就是构造复杂网络的拓扑结构。实际中,在某一种特定网络拓扑结构上表现良好的路由协议或算法,在网络拓扑发生重大变化或移植到另一个不同的网络时,往往不能表现同样良好的性能并且不同的拓扑构造方法所生成的拓扑图不同,因此对网络的性能造成很大的影响,因此,为了仿真在真实网络环境下的拓扑结构特性,需要构造与真实网络相同的拓扑结构，并对网络进行一些可靠分析，进行随机故障和故意攻击的测试。

目前常用的网络拓扑模型包括以下几种：（1）简单规则的拓扑结构,如星型连接、环型连接、树型连接、网格结构等；（2）众所周知的拓扑结构, 如ARPANET,NFSNET,MCI主干域等；（3）随机生成的拓扑结构,如完全随机网络模型[1]，动态随机拓扑模型[2,3],Waxman模型[4,5]等。本文利用度优先准则和距离优先准则构造一类局域网作为测试局域网，求出网络的割边并进行加固，最后对网络进行了测试。

2 测试局域网的构造

测试局域网的构造步骤如下，水平方设置m个点，垂直方向設置n个点，在平面上设置mn个网格节点。随机地取N1个网格节点作为网络的初始节点，节点（xi,yi）和节点（xj,yj）的距离为 接着利用Prim算法构造这N1个节点的最小生成树。然后执行下面两个步骤中的一个。

（1）以概率p（0≤p≤1）增加一个新节点。新节点与网络中离它最近的m1（m≤m0）个节点相连接。

（2）以概率1-p增加一个新节点。新节点根据优先连接概率

重复上面的（1），（2）操作，直到网络中的节点总数达到N2时，算法终止。

仿真时参数的取值如下，m=n=100，N1=20，p=0.3，m1=3，m2=2，N2=100。仿真图见图1。Matlab软件所画的网络图，不便于观察节点之间的关系，用Pajek软件对图1的网络进行可视化的效果见图2。

3 随机故障和故意攻击的测试

为了测试我们构造网络的可靠性，随机地删除10%节点后，网络仍然是连通的，效果图见图3。删除度最高的10%节点后，网络就不连通了，有多个分支，其效果图见图4，说明网络面临故意攻击，其枢纽很容易被破坏，从而造成网络的崩溃。

4 结论

本文构造了一种局域网，并用Matlab软件进行了仿真，为了加强网络的可靠性，我们对网络中的割边进行了加固，测试了所构造的网络对于随机故障和故意攻击的鲁棒性。

用Matlab实现复杂网络的仿真并不困难。与其它语言相比，Matlab语言有丰富的工具箱函数，能够写出简约的代码。对于非计算机专业的大学生、研究生和科研人员，能够快速进入复杂网络前沿研究课题，对其科研能力的培养极为有益。

参考文献

[1] Bollobás B. Random Graphs, New York: Academic Press, 2nd ed., 2001.

[2] 汪小帆，李祥，陈关荣，复杂网络理论及应用，北京：清华大学出版社[M]，2006: 27-29.

[3] 吕国英主编，任瑞征，钱宇华参编，算法设计与分析（第2版），清华大学出版社[M]，2009: 199.

作者简介：

荆平（1966-），山东烟台人，烟台南山学院电气信息实验中心工程师，研究方向：自动化。

李永明（1987-），山东菏泽人，烟台南山学院助理实验师，技师，研究方向：机电一体化。

韦利春（1985－），男，汉族，山东德州人，本科，烟台南山学院高级技师，研究方向为实训教学。

高红慧（1985－），女，汉族，吉林白城人，本科，烟台南山学院助教/技师，研究方向为自动化控制。