基于邻接矩阵的网络流量检测点设置算法

在研究网络流量的有效测量问题时,考虑网络节点的流守恒,把网络流量监测点问题抽象为无向图的最小弱顶点覆盖问题,这是一个NP难的问题.基于图论中邻接矩阵的概念,提出一个近似算法,通过重复删除邻接矩阵中所有行元素之和不超过1的节点对应的行和列,得到最小弱顶点覆盖集.在此基础上通过预先递归去除无向图中1度节点,满足任意节点度数都大于或等于2的最小弱顶点覆盖问题求解条件,并将递归节点作为该近似算法的入口点.仿真实验表明,与现有算法相比,新算法具有更好的性能,能够发现更小的弱顶点覆盖集.

An Algorithm for Seeking Monitor-Nodes Measuring Network Traffic Based on Adjacency Matrix

To research the efficient measurement of the network traffic,considering the equation of the flow conservation,seeking monitor-nodes is regarded as the problem of finding out the minimum weak vertex cover of a graph,which is NP-hard.An approximation algorithm is proposed based on the concept of adjacent matrix in graph,and the algorithm finds out the minimum weak vertex cover set by repeatedly deleting the rows and columns of the nodes whose line element amount is not more than one.By recursively eliminating one out-degree nodes before executing the algorithm,the conditions of finding out the minimum weak vertex cover are met:there are not more than or equal to two out-degree nodes in the graph,and the recursive nodes are selected as the entrance of the algorithm.The simulation results show that the novel algorithm is more efficient than the traditional algorithms,and it can find smaller weak vertex cover.