一种基于顶点覆盖和弱顶点覆盖的探针部署方法

摘要

本发明涉及一种基于顶点覆盖和弱顶点覆盖的探针部署方法，包括：确定测试探针的数量及所述测试探针在网络中的部署位置。本发明提出一种基于顶点覆盖和弱顶点覆盖的探针部署技术，其优点在于，该技术立足于对最小顶点覆盖问题的贪心算法，在该算法的基础上加以改进，提出了基于顶点覆盖和弱顶点覆盖的探针部署算法。首先使用最小顶点覆盖，使得在可以得到每一条链路流量的条件下，所需流量监测器数目最小。之后改进为最小弱顶点覆盖。仿真表明，与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简单，耗时更短，是一种更优秀的网络流量监测探针部署方案。

主权项

一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在于，包括：确定测试探针的数量及所述测试探针在网络中的部署位置；其中，确定测试探针的数量及所述测试探针在网络中的部署位置的步骤为：S1.对网络中所有节点的度排序，得到同时满足前k‑1个节点的度的和小于链路数和前k个节点的度的和大于链路数条件的k；S2.将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无解将k加1，重新进入S2，如果有可能有解则插入到优先队列中；S3.若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4，如果优先队列为空则将k加1，重新进入S2；S4.判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入S5；S5.检查当前节点是否可以扩展，不能扩展的话便进入S3继续循环，如果能扩展的话则扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后进入S3继续循环；确定测试探针的数量及所述测试探针在网络中的部署位置的步骤为：S1.先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；S2.选取一个包含的链路数目最多的节点，记为v_i；S3.删去关联矩阵中v_i对应的行及该行中值为1的元素所在的列；然后在剩下的关联矩阵中再依次删除所有行元素之和不超过1的其他行及这些行中值为1的元素所对应的列，直到不能再删除新的行和列为止；S4.重复S2，S3的操作，直到所有的链路都被包含到。