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

摘要：

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

关键词： 网络流量检测 检测点选取 弱顶点覆盖 近似算法

作者: 石恒华 何泾沙 许鑫

作者单位: 北京工业大学计算机学院,北京 100124 北京工业大学软件学院,北京 100124

会议类型: 国内会议

会议名称: 第十六届全国网络与数据通信学术会议(NDCC2008)

会议地点: 南京

会议语种:中文

页码: 127-130

在线出版日期: 2008-11-10（万方平台首次上网日期，不代表论文的发表时间）