基于邻接矩阵的网络流量检测点选取算法研究

Algorithm research for selecting measurement nodes in measuring network traffic based on adjacency matrix

为对网络流量进行有效检测,考虑网络节点的流守恒,把网络流量检测点选取问题抽象为无向图的弱顶点覆盖问题.基于图论中邻接矩阵的概念,在满足对任意顶点度数大于2的假设条件下,提出一个求解弱顶点覆盖问题的近似算法.通过将求解弱顶点覆盖集中点与边的关系转化为点与点的关系,降低了矩阵计算复杂度.仿真实验表明,与现有算法相比,新算法能够选取出更小的弱顶点覆盖集,部署更少的网络流量检测点,减轻了由网络流量数据收集造成的额外负担.

To efficiently measure the network traffic, considering the flow-conservation equation, the problem of selecting measurement nodes is regarded as a problem of finding out the weak vertex cover of a graph. Under the assumption that the degree of each node is more than 2, an approximate algorithm is proposed based on the concept of adjacency matrix in graph. This algorithm decreases the computation complexity by turning the link-node relationship of the weak vertex cover to a node-node relationship. The simulation results show that the novel algorithm can find smaller weak vertex cover and allocate less measurement nodes, therefore reduce the additional network load for collecting network traffic data.