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

Abstract: 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.

Key words: network topology, network monitoring, weak vertex cover of graph, network expansion, selection algorithm of monitoring points