基于蚁群算法的网络故障定位方法

王育玲　王　慧　刘昌华

(武汉轻工大学数学与计算机学院　武汉　430023)



基于蚁群算法的网络故障定位方法

王育玲王慧刘昌华

(武汉轻工大学数学与计算机学院武汉430023)

随着网络技术的发展和演变,网络设备的正常运行是满足用户业务的最基本需求,也是网络业务正常运行的关键。为此,论文提出以蚁群算法快速查找网络故障,它利用设备信息素浓度强弱判断网络设备故障概率,根据信息素浓度构造业务故障路径。

蚁群算法; 网络故障; 故障路径; 信息素浓度

Class NumberTP301.6

1　蚁群算法

蚁群算法[1]是利用蚂蚁寻找食物的行为,而进行模仿的算法,该算法是由意大利科学家M.Dorigo等提出的,普遍被用在旅行商问题、规划图问题、POS问题、车辆路径问题、网络路由问题等用来查找最优路径,已经成为最前沿的热点和课题。

蚁群算法在网络故障定位中应用,其思想是利用蚂蚁的信息素[3]更新机制去搜索故障方向,寻找故障源,构造业务故障路径。例如在一个公司内部网络设备是固定的,将蚂蚁分布在每个网络设备上,利用蚂蚁分泌的信息素浓度去循环遍历查找业务故障源[4]。当一个业务在网络设备上运行时,网络设备上的流量拥塞[5],导致业务响应慢,这时蚂蚁根据信息素浓度强弱判断该设备出现故障的概率,如果信息素浓度波动幅度较大,则故障出现在该设备上的可能性大,如果信息素浓度在一个范围内平稳波动则该设备出现故障可能性小。

2　蚁群思想的网络故障定位系统模型

当网络业务出现故障,为了更好地描述利用蚁群思想去查找网络故障源,所以给出了两个定义,并提出了网络业务故障定位模型,如图1所示。

定义1通信路径。选择一个具有某业务通信的网络设备节点,从该节点出发,每次选择一个业务信息素浓度低的节点来遍历所有的节点得到的路径称为通信路径,该路径包括每个设备上信息素浓度的强弱。

定义2故障路径。业务通信时设备信息素浓度低于初始化信息素浓度阈值时,就将该设备加入故障路径,遍历整个通信路径,得到的就是故障路径。

网络业务故障定位模型是某一单笔业务出现故障时,利用信息素浓度强弱判断网络通信路径和业务故障路径,如何定位故障源如图1所示。

图1　网络业务故障定位模型

如图1所示的网络业务故障定位模型,某业务经过设备Source、R1、R2、R3、Destination进行通信,业务通信路径为〈Source、R1、R2、R3、Destination〉,本文是将蚂蚁分布在各个网络设备,同时蚂蚁在网络各个设备分泌浓度相同的信息素,当业务通过设备R3出现故障,到达不了目的网络设备时,设备R3的信息素浓度会下降,同时业务故障路径上的信息素浓度都会下降,而探针[2]的作用就是在设备上做镜像,将信息素浓度最低的设备发给分析器[6],分析器会分析通信设备信息素的浓度高低,并将信息素浓度由高到低排列得到故障路径〈Source、R1、R2、R3〉。

3　蚁群思想的故障路径构造算法

在构造网络故障路径机制中,将企业中每个网络设备设定一个坐标(X,Y),该坐标可以根据网络拓扑[7]的变更而变化,运算机制是随机邻近查找[8],给每个网络设备设置一个网络坐标,由于每个坐标是不一样的,所以可以将每个设备的坐标看作是一只蚂蚁,每只蚂蚁利用信息素更新机制获取网络故障路径,其获取网络故障路径的步骤如下:

第1步:初始化网络设备编号代码。

For(i=0;i

{Ant[i]=++i;}

第2步:根据式(1)初始化通信路径上的信息素强度。

Sij=1/ADij

(1)

其中,ADij是由矩阵表示的两两网络元设备之间的距离。

第3步:根据式(2)计算两个网络设备之间的距离。

(2)

其中,Cij是网络设备坐标。

第4步:根据式(3)计算由矩阵表示两两网络设备元之间的距离:

SD=ADij=CDji

(3)

第5步:根据式(4)获取经过的网络设备的路径长度:

(4)

第6步:根据式(5)得到当前网络设备节点到下一个节点转移的概率:

(5)

其中,Wij是网络设备节点的信息素强度,Vij是网络设备节点之间的能见度,α是信息启发因子,β是期望启发因子。

第7步:根据式(6)计算信息素浓度,用来制定更新规则:

(6)

其中,α是信息启发因子,υ是全局信息素挥发参数,L为矩阵表示的两设备节点之间的距离。

不失一般性,假设在一个企业网络中,是由N台网络设备构建的一个网络拓扑,且与外网互联互通,首先给每个网络设备初始化一个坐标,形成一个坐标矩阵,根据矩阵C[N][2]初始化一个网络设备编号,并将蚂蚁均匀分布在每个网络设备上。在每台设备上根据式(1)初始化信息素浓度,初始化信息素浓度的作用是为了方便查找故障设备,当业务故障时,该业务路径上设备的信息素浓度会下降,探针可以快速获取信息素浓度低的设备。网络设备之间的距离是用式(2)计算,网络设备之间长度利用式(4)计算,并根据式(3)将其真实的距离和长度映射到矩阵上,方便进行仿真实验。蚂蚁在设备上转移的概率[9]有式(5)根据信息素浓度确定是否转移。但是随着时间的推移网络信息素浓度会下降,但不会降到零。所以每个设备都有信息素浓度更新机制,它能有效地控制信息素浓度在一个小范围内波动,其利用的是式(6)。此方法的好处是当网络故障时不需要知道业务设备之间的上下游关联性[10],只要知道某设备的信息素浓度最低就可以快速定位故障的网络设备。

3.1实验数据

网络设备坐标的仿真数据如表1所示,选自VC++数据实例。

表1　仿真数据

3.2仿真实验结果

根据网络设备上信息素浓度确定网络故障路径,网元设备30个,由实验数据(1)迭代次数500次后得到信息素浓度从高到低的网络设备排列顺序,如图2所示。利用Matlab仿真得到网络通信路径和故障节点(空心的为故障节点),如图3所示。

图2　计算的故障路径

图3　故障节点(空心)

根据网络设备上信息素浓度确定网络故障路径,网元设备30个,由实验数据(2)迭代次数1000次后得到信息素浓度从高到低的网络设备排列顺序,如图4所示。利用Matlab仿真得到网络通信路径和故障节点(空心的为故障节点),如图5所示。

图4　计算的故障路径

图5　故障节点(空心)

4　结语

实验证明用蚁群算法定位网络故障,可以快速定位网络设备故障,但是在网络应用方面不能精确定位故障源,因为IP网络是由成千上万的业务组成,单笔业务经过二层交换机、三层交换机、路由器、核心网络、服务器、应用程序等硬件和软件,造成业务故障(性能:延迟、丢包)的因素有可能是设备故障、链路拥塞、应用错误、配置错误,而且单笔业务分片发送到目的数据包也可能不走同一路径,所以网络故障定位不能仅仅只定位设备故障,而定位应用故障的方法却有待进一步研究。

[1] V Maniezzo, A Carbonaro. Ant Colony Optimization: an over view[C]//C Ribeiro. Essays and Serverys in Metaheuristics, Kluwer,2001:21-44.

[2] 熊国江.基于计算智能的电网故障诊断方法研究[D].武汉:华中科技大学,2014:10-19.

XIONG Guojiang. A Power Grid Fault Diagnosis Method Based on Computational Intelligence[D]. Wuhan: Huazhong University of Science and Technology,2014:10-19.

[3] 冼学辉,张悦,程海燕.蚁群算法在WSN QoS路由中的优化研究[J].计算机仿真学报,2015,11:395-398.

XIAN Xuehui, ZHANG Yue, CHENG Haiyan. Ant Colony Algorithm in WSN QoS Routing Optimization[J]. Journal of Computer Simulation,2015,11:395-398.

[4] 周萍.计算机网络故障的一般识别与解决方法分析[J].科技传播学报,2015,12:121-135.

ZHOU Ping. The General Identification and Solution Method of Computer Network Fault Analysis[J]. Journal of Science and Technology Communication,2015,12:121-135.

[5] 周杰.TCP协议两种典型拥塞控制算法的比较与仿真[J].齐齐哈尔大学学报(自然科学版),2016,1:27-29.

ZHOU Jie. Comparison and Simulation of Two Typical Congestion Control Algorithms for TCP Protocol[J]. Journal of Qiqihar University(Natural Science Edition),2016,1:27-29.

[6] 汪雷.东煤勘探局内网网络协议分析器设计与实现[D].长春:吉林大学计算机学院,2014,6:12-27.

WANG Lei. Design and Implementation of Network Protocol Analyzer for East Coal Exploration Bureau[D]. Changchun: College of Computer Science, Jilin University,2014,6:12-27.

[7] 蔡文哲,王斌君.一种QoS平面蚁群路由算法的设计与实现[J].计算机与现代化,2015,12:1-5.

CAI Wenzhe, WANG Binjun. A QoS Routing Algorithm for Plane Network Based on Ant Colony Algorithm[J]. Computer and Modern,2015,12:1-5.

[8] 李媛祯,杨群,段汐.基于均衡更新蚁群算法的飞机排序调度[J].计算机与现代化,2015,2:1-3.

LI Yuanzhen, YANG Qun, DUAN Xi. A Balanced Update Ant Colony Optimization for Aircraft Arrival Sequencing and Scheduling[J]. Computer and Modern,2015,2:1-3.

[9] 于红斌,张志军,苏沛.基于趋化行为的改进蚁群算法及路径规划应用[J].微处理机,2015,8:1-6.

YU Hongbin, ZHANG Zhijun, SU Pei. An Improved Ant Colony Algorithm Based on Chemotaxis and Application in Path Planning[J]. Microprocessor,2015,8:1-6.

[10] 徐昊,吴明慧,刘伟.基于动态路由与蚁群优化的移动无线自组织网络算法[J].计算机应用研究,2015,9:3-6.

XU Hao, WU Minghui, LIU Wei. Dynamic Routing and Ant Colony Based Approach of MANET[J]. Computer Application Research,2015,9:3-6.

Network Fault Location Method Based on Ant Colony Algorithm

WANG YulingWANG HuiLIU Changhua

(College of Mathematics and Computer Science, Wuhan Polytechnic University, Wuhan430023)

With the development and evolution of network technology, the normal operation of network equipment is the most basic needs of the needs of business users and the key of the normal operation of network services. Therefore, this paper proposes to find a network failure quickly with ant colony algorithm, which uses equipment pheromone concentration to determine the strength of the network devices failure probability, according to the pheromone concentration the business failed path is constructed.

ant colony algorithm, network failure, failed path, pheromone concentration

2016年2月12日,

2016年3月20日

湖北省自然科学基金资助项目:流控制传输协议的拥塞控制新型计算模型研究(编号:2009Chb008)资助。

王育玲,女,硕士研究生,研究方向:网络安全。王慧,女,硕士研究生,研究方向:软件开发。刘昌华,男,副教授,硕士生导师,研究方向:计算机网络及应用、嵌入式FPGA设计。

TP301.6

10.3969/j.issn.1672-9722.2016.08.004