增量网络监测点的增量选取算法  

Incremental selection algorithm for incremental network monitoring points

作　　者：丁三军[1] 陶兴宇 石祥超[1] 徐蕾[2] 

机构地区：[1]沈阳飞机设计研究所,沈阳110035 [2]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《计算机应用》2015年第12期3344-3347,共4页journal of Computer Applications

基　　金：中航工业技术创新基金(基础研究类)资助项目(2013S60109R)

摘　　要：针对网络拓扑结构扩充后,原有网络中布置的监测点不易变动的问题,提出一种增量网络监测点的增量选取算法。该算法优化了以网络中顶点的度数作为贪心选择策略求解图的弱顶点覆盖的贪心算法,从而得到更少顶点的近似解。在计算增量网络监测点集时,该算法只利用新增网络拓扑得出新增网络的监测点集,求得的增量监测点可直接加入到原网监测点集合中得到新的全网监测点集,降低重新布置全网监测点的成本。实验结果表明,增量算法得到的全网监测点集与在全新的网络中重新计算得到的全网监测点集的顶点数基本相同,可有效应用于实际的网络监测点部署。In order to resolve the difficulty in changing the monitoring points of the original network after extending the network topology structure, an incremental election algorithm for incremental network monitoring points was proposed. The greedy algorithm was optimized by the proposed algorithm to obtain the approximate solution of fewer vertices, which used the degree of vertices in the network as the greedy-choice strategy for the weak vertex cover of the graph. While calculating incremental network monitoring point set, only the extended network topology was used to obtain the corresponding monitoring point set of the new network. The obtained incremental monitoring points could be directly added to the collection of the original network monitoring points for the new whole network monitoring point set and the cost of rearranging the whole network monitoring points could be reduced. The experiment results show that the number of vertices of the whole monitoring point set obtained by the proposed incremental selection algorithm is basically the same with that of a new monitoring point set generated by recalculating the whole network topology structure in the new network. The proposed algorithm can be effectively applied to the deployment of actual network monitoring points.

关 键 词：网络拓扑 网络监测 图的弱顶点覆盖 网络扩充 监测点选取算法 

分 类 号：TP393.07[自动化与计算机技术—计算机应用技术]