一种基于顶点覆盖和弱顶点覆盖的探针部署方法
一种基于顶点覆盖和弱顶点覆盖的探针部署方法
【技术领域】
[0001] 本发明属于基于探针的网络流量检测技术，是一种能够实现对数据网的网络层的 全面检测的探针部署方法。
【背景技术】
[0002] 针对网络流量监测的业务需求，可W使用化tFlow的探测方式。在网络中某一节点 设置探针可W得到与运一节点相联的所有链路上的流量。因此，为了得到网络中所有链路 的网络流量，一般可W通过在某些交换节点（路由器)配置监测器实现，我们要考虑的问题 是:在网络哪些节点上设置监测器，才能使得在可W得到每一条链路流量的条件下，所需流 量监测器数目最小。
[0003] 通过探针，实现对数据网的网络层对业务的全面监测。若是全覆盖，不仅成本高， 而且在测量时也会产生大量测量数据，造成噪声。在η个网元组成的网络中，测量k个网元间 的流量特征，需要从η个中挑出k个网元，另外，考虑到流向问题，还需考虑k个节点的排列组 合，测量方案就需要C(n，k)P化，k)。若是按照此全覆盖的测量方式和方案造成的时间复杂 度为阶乘级的，空间复杂度也很庞大。围绕着业务监测的需要出发，研究如何部署适量的探 针W满足不同的业务监测需求，W解决部署位置和部署容量的问题。
[0004] 为了解现有技术的发展状况，对已有的论文和专利进行了检索、比较和分析，筛选 出如下与本发明相关度比较高的技术信息：
[0005] 技术方案1:专利号为CN103138833A的《基于流量监测的P0N中网络编码配对关系 管理方法》专利，设及通信技术领域，主要通过Ξ步完成:第一，0LT建立起存在双向数据传 输的0NU对的网络编码连接关系，当化T检测到此0NU对的双向数据流交互后，即可开始网络 编码过程;第二，0LT基于0NU标识符统计所有存在双向数据传输的0NU对，并采用一定的算 法，将双向数据流量大小转化为对应的影响因子;第S，0LT实时监控影响因子的变化情况， 如果当未参与网络编码0NU对的影响因子IFn大于参与网络编码0NU对的影响因子I化时，贝U 拆除I巧对应的网络编码对，同时为I化对应的0NU对建立网络编码连接。
[0006] 技术方案2:专利号为CN102781014A的《基于无线传感器网络和3G网络的智能流量 监测方法》专利，设及传感器采集的流量数据与无处传感器网络信息的无缝连接技术、 802.15.4协议与TCP/IP协议之间协议转换技术。数据采集模块采集不同流体介质、管径等 动态变化的参数，采集的参数值通过异步传输方式传送至无线传感器网络的ZigBee无线通 信模块，再传输至微处理器模块进行参数的处理和运算，最后通过3G网关传输至上位机监 控中屯、，实现远距离流量监测、管理。
[0007] 技术方案3:专利号为CN103036741A的《流量监测基线的确定方法及装置》专利，设 及一种流量监测基线的确定方法及装置，在直角坐标平面内确定预设周期内的历史流量数 据图，所述直角坐标平面内的第一坐标轴表示所述预设周期内的时间，所述直角坐标平面 内的第二坐标轴表示所述历史流量数据;根据所述历史流量数据图与所述第一坐标轴和所 述第二坐标轴围成的区域，在所述坐标平面内确定基线绘制区域;在所述基线绘制区域内， 接收用户根据所述历史流量数据图触发的鼠标事件;根据所述鼠标事件在所述基线绘制区 域内的坐标位置，确定流量监测基线值。该装置包括:第一处理模块、第二处理模块、接收模 块和第Ξ处理模块。
[0008] 技术方案1能实时地根据0NU流量大小特点确定是否适合参与网络编码，从而找到 参与网络编码的最佳网络编码对，提高网络带宽的利用率，进一步减小了网络的拥塞。只是 在流量监测的基础上进行编码，并没有重点研究如何进行流量监测。技术方案2采用有线与 无线相结合的方式，节省了大量用于巡视、抄表的人力物力，提高了自动化程度管理水平， 实现了流量监测的低功耗、低成本、自动化、网络化、智能化。但是该方案的智能流量监测方 法基于无线传感器网络和3G网络，成本较高，且容易造成数据拥塞，并没有考虑优化问题。 技术方案3可W准确确定流量监测基线值，避免误报和漏报。重点在于研究流量检测极限值 的确定，并没有具体的研究流量监测的方法。
【发明内容】
[0009] 本发明正是为了克服上述缺陷而提供的一种基于顶点覆盖和弱顶点覆盖的探针 部署方法。本发明的目的在于研究基于贪屯、策略的探针部署方法，通过对最小顶点覆盖问 题的贪屯、算法进行改进，通过分支限定法的贪屯、策略实现探针部署问题。它可保证算法更 简便，耗时更短，而且使用探针数更少。
[0010] 本发明首先提出基于最小顶点覆盖的探针部署方案，实验表明，该算法能求得最 小顶点覆盖的最优解，但其计算复杂度高，花费时间长，并不能应用到大规模问题中。而且 最小顶点覆盖的最优解并不一定是网络流量监测探针部署的最优解。为此在最小顶点覆盖 的探针部署方案的基础上加 W改进，提出了基于最小弱顶点覆盖的探针部署方案，与基于 最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简单，耗时更短，是 一种更优秀的网络流量监测探针部署方案。
[0011] 本发明是通过如下技术方案来实现的：
[0012] -种基于顶点覆盖和弱顶点覆盖的探针部署方法，本发明特征在于，包括:确定测 试探针的数量及所述测试探针在网络中的部署位置。
[0013] 在基于定点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针在网络 中的部署位置的步骤为：
[0014] S1.对网络中所有节点的度排序，得到同时满足前k-1个节点的度的和小于链路数 和前k个节点的度的和大于链路数条件的k;
[0015] S2.将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无 解将k加1，重新进入S2，如果有可能有解则插入到优先队列中；
[0016] S3.若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4,如 果优先队列为空则将k加1，重新进入S2;
[0017] S4.判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入 S5；
[0018] S5.检查当前节点是否可W扩展，不能扩展的话便进入S3继续循环，如果能扩展的 话则扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后 进入S3继续循环。
[0019] 在基于最小弱顶点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针 在网络中的部署位置的步骤为：
[0020] S1.先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；
[0021 ] S2.选取一个包含的链路数目最多的节点，记为Vi;
[0022] S3.删去关联矩阵中VI对应的行及该行中值为1的元素所在的列;然后在剩下的关 联矩阵中再依次删除所有行元素之和不超过1的其他行及运些行中值为1的元素所对应的 列，直到不能再删除新的行和列为止；
[0023] S4.重复S2，S3的操作，直到所有的链路都被包含到。
[0024] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 使用最优队列和空间树来建立模型；在建立模型之后，确定测试探针的数量及所述探针在 网络模型中的部署位置。
[0025] 本发明中，使用最优队列和空间树来建立模型，包括：
[0026] 用一个优先队列维护当前可行的节点，每个节点维护着该节点情 况下还可W选择 的顶点数目ki、需要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，运些 节点按顶点的边数从大到小排序，其中对于顶点的状态，该策略中顶点有立种状态，分别为 已经选择了的状态S1，不选择的状态S2，可W选择的状态S3，其中，已经选择了的状态S1对 应解空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态si;不选择的状态 s2对应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态s2;可W选择的 状态S3对应解空间树中的父节点，选择该节点，然后设置该节点为可W选择状态s3;sl和s2 都是已经确定的状态，节点的选取只能从S3中选取。
[0027] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 建立基于最小弱顶点覆盖的检测模型；在建立模型之后，确定测试探针的数量及所述探针 在网络检测模型中的部署位置。
[0028] 本发明中，建立基于最小弱顶点覆盖的检测模型，包括：
[0029] 建立一个节点与链路的关联矩阵，该矩阵W链路为列，W节点为行，若该链路包括 该节点，则对于的值为1，否则为0。
[0030] 通过探针，实现对数据网的网络层对业务的全面监测。若是全覆盖，不仅成本高， 而且在测量时也会产生大量测量数据，造成噪声。在η个网元组成的网络中，测量k个网元间 的流量特征，需要从η个中挑出k个网元，另外，考虑到流向问题，还需考虑k个节点的排列组 合，测量方案就需要C(n，k)P化，k)。若是按照此全覆盖的测量方式和方案造成的时间复杂 度为阶乘级的，空间复杂度也很庞大。
[0031] 围绕着业务监测的需要出发，研究如何部署适量的探针W满足不同的业务监测需 求，W解决部署位置和部署容量的问题。要求解决的部署实例为"某数据网拓扑图"。
[0032] 1.假设问题中的数据网内的链路权值都相等，假设为1;
[0033] 2.假设问题中网元间的通信路由规则采用最短路算法；
[0034] 3.在最小弱顶点覆盖模型中，假设一个网元可W监测与其直接相关的所有链路的 流量，且满足流量守恒；
[0035] 4.在最小集合覆盖模型中，假设任意两网元可W通过通信监测其路径上的所有链 路的状态，网络监测命令发生在探针与探针之间；
[0036] 5.由于网络边缘节点的度数通常较小，若把探测站点的位置选定在网络的边缘 处，那么从该探测站点发送出的探测的数目W及探测的能力就会收到相应的限制，因而假 设探针位置不会在网络的边缘。
[0037] 针对网络流量监测的业务需求，可W使用化tFlow的探测方式。在网络中某一节点 设置探针可W得到与运一节点相联的所有链路上的流量；因此，为了得到网络中所有链路 的网络流量，一般可W通过在某些交换节点（路由器)配置监测器实现，我们要考虑的问题 是:在网络哪些节点上设置监测器，才能使得在可W得到每一条链路流量的条件下，所需流 量监测器数目最小。
[0038] 使用最小顶点覆盖可W解决运一问题。顶点覆盖问题已被证明是NP完全的，只能 用近似算法算出近似最优解。我们本文中对最小顶点覆盖问题的贪屯、算法进行改进，通过 分支限定法的贪屯、策略实现探针部署问题。
[0039] 在考虑到网络监测方式的同时，加上流量守恒的约束，使用最小弱顶点覆盖能够 部署更少的探针来实现整个网络的网络流量监测。同样最小弱顶点覆盖问题也已被证明是 NP完全的，也是只能使用近似算法求近似最优解。我们运里使用贪屯、策略来实现探针部署 问题。
[0040] 对于流量监测测试的评估指标：
[0041] 1.部署的探针的个数；
[0042] 2.链路覆盖率。
[0043] 我们需要把需要部署探针的网络图转化为无向图G(V，E)，其中ν=(νι，ν2，···，νη) 为网络节点集(在IP网络中可看作为路由器），E=(el，e2，…，em)为网络中的链路集合。其 中，n= |V|，m= |E|分别表示G中节点和链路的数目。用ek=(vi，vj)表示ek是连接节点Vi和vj 的一条链路。
[0044] 用De gr e e (V)表示节点V的链路数，即节点V的度。
[0045] 把原始网络图的所有路由器，交换机等设备按照1，2,……的顺序标号，然后统计 所有的链路信息，将该图转化为无向图。该网络有160个节点，185条链路。是一个稀疏图（边 的条数m远小于η 2的图），可W用邻接链表来表示无向图，但是考虑一般情况，为了能够解决 各种的图，使用邻接矩阵来表示无向图。
[0046] 首先介绍基于最小顶点覆盖的探针部署方案：
[0047] 根据下面定义，可W很方便的描述问题模型
[004引定义1:给定无向图G(V，E)，其中V是顶点集，Ε是边集，S是V的子集，若根据与S中顶 点相关联的各条边的流量，可W确定E中任意边的流量，则称S是图G关于流量的测量集。
[0049] 有效测量问题的目标就是求给定图G关于流量的最小测量集。可W转换为求定义2 中图G的最小顶点覆盖问题。
[0050] 定义2(最小顶点覆盖问题）：指给定一个无向图G(V，E)，求顶点集V的一个最小子 集S，使得e = (u，v)eE，且ueS或veS，即E中的任一边至少含有此子集中的一个点作为顶 点，也就是说S中的顶点覆盖了边集E。
[0051] 其数学描述为：
[0化2] min CX其中xiES
[0化3]
[0054] 其中c=[l，l，···，υ和X=[X1，X2，···，XrJ都是长为η的向量，（aij)nXn是图的邻接矩 阵，且
[0化5]
2
[0056] 最小顶点覆盖问题已被证明是NP完全的，到目前为止还不存在多项式时间算法来 求解，我们可W用贪屯、算法去求出近似最优解，即每次迭代都选取度最大的节点作为探针， 然后所有与其相连的节点都可W排除掉，满足每次选取探针都是当下情况的最优情况，但 是考虑到每次的最优并不一定能得到整体上的最优，为了找到更小的解，通过下面的限定 策略，我们对贪屯、进行改进，通过分支界限法来得到更优解。
[0057] 对所有节点的度从大到小排序，取前k个节点，满足
[0化引
.3.
[0059] 时，是可能满足顶点覆盖的界限。
[0060] 通过上述约束，我们在使用贪屯、算法之前，先求出一个最小可能的最优解k，将问 题转化为判定无向图中是否存在k个节点满足最小顶点覆盖。通过贪屯、策略和限定策略去 判定，若满足则k是最优解，若不满足则将k加1，继续判定。
[0061 ]在介绍具体的判定过程之前，首先使用最优队列和空间树来建立模型，用一个优 先队列维护当前可行的节点，每个节点维护着该节点情况下还可W选择的顶点数目ki、需 要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，运些节点的排序遵循贪 屯、策略，按顶点的边数从大到小排序。对于顶点的状态。该策略中顶点有Ξ种状态，分别为 已经选择了的状态S1，不选择的状态S2,可W选择的状态S3。其中，已经选择了的状态S1对 应解空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态S1;不选择的状态 S2对应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态S2。可W选择的 状态S3对应解空间树中的父节点，选择该节点，然后设置该节点为可W选择 状态S3"S1和S2 都是已经确定的状态，节点的选取只能从S3中选取。
[0062] 取出最优队列里的第一个节点进行扩展：
[0063] 将该节点设置为S1，同时按照公式4修改该节点的信息，然后把该节点放入空间树 的左节点;再将该节点设置为S2,不用修改其他节点信息直接放入空间树的右节点。
[0064] ki = ki-l, e = e-De邑ree ,De邑ree = 0 4
[00化]通过约束条巧
先对右节点判定，若满足，将该点插入最优队列； 再选取左节点进行判定，若满足，将该节点插入最优队列。
[0066] 对上面步骤的迭代就是具体的判定过程。
[0067] 相应的流程图如图1所示。
[0068] 在基于最小顶点覆盖的探针部署算法的基础上加 W改进，提出了基于最小弱顶点 覆盖的探针部署算法：
[0069] 在定义1的基础上，由于探针设置在路由器或交换机等交换设备上，根据流量守 恒，那么图G还满足W下两条约束条件：
[0070] 1.对图G的顶点集V中的任意顶点V，其度Degree(v) > 2;
[0071] 2.对图G的顶点集V中的任意顶点V，满足流守恒方程，即流进=流出。
[0072] 尽管W下原因会将导致流守恒方程的失真，如:交换设备是数据的源或汇，而不仅 仅是数据转发器;多播导致输出端口的数据复制;交换设备本身的数据包延迟或丢失。但是 若干研究表明，流守恒方程所具有的相对误差小于0.05%。
[0073] 定义3(弱顶点覆盖）：假定无向图G(V，E)目满足对任意veV有Degree(v) >2,称 《cr是图G的弱顶点覆盖集，当且仅当执行W下操作能使E中所有的边都可W被标记：
[0074] (1)标记所有与S中顶点相关联的边；
[0075] (2)若某个顶点V的Degree(v)-1条相关联的边己被标记，则标记剩下的那条相关 联的边；
[0076] (3)重复第(2)步，直到不能再标记新的边为止。
[0077] 显然，由此弱顶点覆盖S就可W得到图G中各链路的流量。本文利用关联矩阵的概 念建立求解弱顶点覆盖问题的模型，为此先给出W下定义。
[007引定义4(关联关系)在无向图G(V，E)中，若vEV是eEE的顶点之一，贝嚇V与e之间存 在着关联关系，记为vRe
[0079] 定义5(关联矩阵）图G(V，E)的关联矩阵A=(au)是
[0080] 指如下定义的η Xm矩阵：
[0081]
3
[0082] 根据关联矩阵的定义，可知V的一个子集构成图G的一个覆盖，当且仅当在它包含 的节点所对应的关联矩阵的行中每列至少存在一个1。
[0083] 根据W上分析，采用贪屯、算法可W求解弱顶点覆盖问题，需要注意的是我们的网 络图中的边界点度为1，并不满足条件约束1，所W我们需要对无向图进行预处理。
[0084] 对于初始情况下度为1的顶点VI，只有一个边与该点存在关联，该边记为ej响的另 一个顶点记为Vj。
[0085] 当vj只有一个度为1的邻顶点VI，只要得出vj其他相关边的流量信息就能根据流量 算出eu的流量。即vj满足最小弱顶点覆盖，只是计算该边的度需要把eu加上;或者vj是探针 部署位置时也直接能监测到eu的流量。
[0086] 当vj有多化|k>l)个度为1的邻顶点，若不把节点V六受为探针，则至少需要设置k个 探针，所W只有将节点Vj设为探针，才能保证部署探针目数最少。
[0087] 根据上面分析，可知初始情况度为1的节点可W都不设探针，可W直接被舍弃，但 预处理舍弃一个度为1的节点时，不将其他与其相连的节点的度减1。
[0088] 鉴于上述基于最小弱顶点覆盖的流量监测模型，设计其算法流程如下：
[0089] Stepl:先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；
[0090] Step2:选取一个包含的链路数目最多的节点，记为VI;
[0091] Step3:删去关联矩阵中Vi对应的行及该行中值为1的元素所在的列；然后在剩下 的关联矩阵中再依次删除所有行元素之和不超过1的其他行及运些行中值为1的元素所对 应的列，直到不能再删除新的行和列为止；
[0092] Step4:重复Step2，Step3的操作，直到所有的链路都被包含到。
[0093] 相应的算法流程图如图2所示。
[0094] 本发明的技术关键点在于：
[00M] 1、本算法对最小顶点覆盖问题的贪屯、算法进行改进，通过分支限定法的贪屯、策略 实现探针部署问题；
[0096] 2、在考虑到网络监测方式的同时，加上流量守恒的约束，使用最小弱顶点覆盖能 够部署更少的探针来实现整个网络的网络流量监测。
[0097] 本发明的有益效果：本专利提出一种基于顶点覆盖和弱顶点覆盖的探针部署技 术，其优点在于，该技术立足于对最小顶点覆盖问题的贪屯、算法，在该算法的基础上加 W改 进，提出了基于顶点覆盖和弱顶点覆盖的探针部署算法。首先使用最小顶点覆盖，使得在可 W得到每一条链路流量的条件下，所需流量监测器数目最小。之后改进为最小弱顶点覆盖。 仿真表明，与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简 单，耗时更短，是一种更优秀的网络流量监测探针部署方案。
【附图说明】
[0098] 图1为基于最小顶点覆盖的探针部署算法流程图；
[0099] 图2为基于最小弱顶点覆盖的算法流程图。
【具体实施方式】
[0100] -种基于顶点覆盖和弱顶点覆盖的探针部署方法，本发明特征在于，包括:确定测 试探针的数量及所述测试探针在网络中的部署位置。
[0101] 在基于定点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针在网络 中的部署位置的步骤为：
[0102] S1.对网络中所有节点的度排序，得到同时满足前k-1个节点的度的和小于链路数 和前k个节点的度的和大于链路数条件的k;
[0103] S2.将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无 解将k加1，重新进入S2，如果有可能有解则插入到优先队列中；
[0104] S3.若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4,如 果优先队列为空则将k加1，重新进入S2;
[0105] S4.判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入 S5；
[0106] S5.检查当前节点是否可W扩展，不能扩展的话便进入S3继续循环，如果能扩展的 话则扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后 进入S3继续循环。
[0107] 在基于最小弱顶点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针 在网络中的部署位置的步骤为：
[0108] S1.先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；
[0109] S2.选取一个包含的链路数目最多的节点，记为Vi;
[0110] S3.删去关联矩阵中VI对应的行及该行中值为1的元素所在的列;然后在剩下的关 联矩阵中再依次删除所有行元素之和不超过1的其他行及运些行中值为1的元素 所对应的 列，直到不能再删除新的行和列为止；
[0111] S4.重复S2, S3的操作，直到所有的链路都被包含到。
[0112] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 使用最优队列和空间树来建立模型；在建立模型之后，确定测试探针的数量及所述探针在 网络模型中的部署位置。
[0113] 本发明中，使用最优队列和空间树来建立模型，包括：
[0114] 用一个优先队列维护当前可行的节点，每个节点维护着该节点情况下还可W选择 的顶点数目ki、需要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，运些 节点按顶点的边数从大到小排序，其中对于顶点的状态，该策略中顶点有立种状态，分别为 已经选择了的状态S1，不选择的状态S2，可W选择的状态S3，其中，已经选择了的状态S1对 应解空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态si;不选择的状态 s2对应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态s2;可W选择的 状态S3对应解空间树中的父节点，选择该节点，然后设置该节点为可W选择状态s3;sl和s2 都是已经确定的状态，节点的选取只能从S3中选取。
[0115] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 建立基于最小弱顶点覆盖的检测模型；在建立模型之后，确定测试探针的数量及所述探针 在网络检测模型中的部署位置。
[0116] 本发明中，建立基于最小弱顶点覆盖的检测模型，包括：
[0117] 建立一个节点与链路的关联矩阵，该矩阵W链路为列，W节点为行，若该链路包括 该节点，则对于的值为1，否则为0。
[0118] 如表1所示，通过使用分支限定法的最小顶点覆盖模型部署该网络，只需部署43个 探针就能够实现流量监控网络覆盖率100%，即基于最小顶点覆盖的探针部署方案部署43 个探针就可W实现该网络图全图各条边的流量监测。
[0119] 表1评价指标 「01201
[0121] 需要指出的是，尽管分支限定法能求得最小顶点覆盖的最优解，但其计算复杂度 高，花费时间长，并不能应用到大规模问题中。而且最小顶点覆盖的最优解并不一定是网络 流量监测探针部署的最优解，所W为了找到算法更简便，耗时更短，而且使用探针数更少的 部署方案，下面将结合网络流量守恒的性质通过最小弱顶点覆盖来部署探针。
[0122] 如表2所示，通过使用最小弱定点覆盖的方法，只需部署32个探针就能够实现流量 监控网络覆盖率100%。在该种方法中，有部分路径的网络流量是通过流量守恒计算得到 的。
[0123] 表2评价指标
[0124]
[0125] 与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简 单，耗时更短，是一种更优秀的网络流量监测探针部署方案。
[0126] 但是运两种探针部署防案都是被动测试，能够利用端口镜像，多路转发W用链路 串接等方式收集网络中本身传输的数据包，包括业务数据包、信令数据包和管理信息数据 包等，分析网络性能，被动地监测网络性能，有着不增加额外流量，对网络影响很小的优点。
【主权项】
1. 一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在于，包括:确定测试探针 的数量及所述测试探针在网络中的部署位置;其中， 确定测试探针的数量及所述测试探针在网络中的部署位置的步骤为：51. 对网络中所有节点的度排序，得到同时满足前k-1个节点的度的和小于链路数和前 k个节点的度的和大于链路数条件的k;52. 将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无解将 k加1，重新进入S2，如果有可能有解则插入到优先队列中；53. 若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4,如果优 先队列为空则将k加1，重新进入S2;54. 判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入S5;55. 检查当前节点是否可以扩展，不能扩展的话便进入S3继续循环，如果能扩展的话则 扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后进入 S3继续循环； 确定测试探针的数量及所述测试探针在网络中的部署位置的步骤为：51. 先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；52. 选取一个包含的链路数目最多的节点，记为Vi;53. 删去关联矩阵中^对应的行及该行中值为1的元素所在的列;然后在剩下的关联矩 阵中再依次删除所有行元素之和不超过1的其他行及这些行中值为1的元素所对应的列，直 到不能再删除新的行和列为止；54. 重复S2，S3的操作，直到所有的链路都被包含到。2. 根据权利要求1所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在 于，在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 使用最优队列和空间树来建立模型； 在建立模型之后，确定测试探针的数量及所述探针在网络模型中的部署位置。3. 根据权利要求2所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在 于，使用最优队列和空间树来建立模型，包括： 用一个优先队列维护当前可行的节点，每个节点维护着该节点情况下还可以选择的顶 点数目ki、需要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，这些节点 按顶点的边数从大到小排序，其中对于顶点的状态，该策略中顶点有三种状态，分别为已经 选择了的状态si，不选择的状态s2,可以选择的状态S3,其中，已经选择了的状态si对应解 空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态si;不选择的状态s2对 应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态s2;可以选择的状态 S3对应解空间树中的父节点，选择该节点，然后设置该节点为可以选择状态s3;sl和s2都是 已经确定的状态，节点的选取只能从S3中选取。4. 根据权利要求1或2或3所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其 特征在于，在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 建立基于最小弱顶点覆盖的检测模型； 在建立模型之后，确定测试探针的数量及所述探针在网络检测模型中的部署位置。5. 根据权利要求4所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在
【专利摘要】本发明涉及一种基于顶点覆盖和弱顶点覆盖的探针部署方法，包括：确定测试探针的数量及所述测试探针在网络中的部署位置。本发明提出一种基于顶点覆盖和弱顶点覆盖的探针部署技术，其优点在于，该技术立足于对最小顶点覆盖问题的贪心算法，在该算法的基础上加以改进，提出了基于顶点覆盖和弱顶点覆盖的探针部署算法。首先使用最小顶点覆盖，使得在可以得到每一条链路流量的条件下，所需流量监测器数目最小。之后改进为最小弱顶点覆盖。仿真表明，与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简单，耗时更短，是一种更优秀的网络流量监测探针部署方案。
【IPC分类】H04L12/24, H04L12/26
【公开号】CN105490834
【申请号】CN201510807537
【发明人】刘宇明, 田丰, 刘彤, 何林宏, 李辉, 苏进, 李晓耕, 李朝广, 韩熙媛
【申请人】云南电力调度控制中心
【公开日】2016年4月13日
【申请日】2015年11月19日
【技术领域】
[0001] 本发明属于基于探针的网络流量检测技术，是一种能够实现对数据网的网络层的 全面检测的探针部署方法。
【背景技术】
[0002] 针对网络流量监测的业务需求，可W使用化tFlow的探测方式。在网络中某一节点 设置探针可W得到与运一节点相联的所有链路上的流量。因此，为了得到网络中所有链路 的网络流量，一般可W通过在某些交换节点（路由器)配置监测器实现，我们要考虑的问题 是:在网络哪些节点上设置监测器，才能使得在可W得到每一条链路流量的条件下，所需流 量监测器数目最小。
[0003] 通过探针，实现对数据网的网络层对业务的全面监测。若是全覆盖，不仅成本高， 而且在测量时也会产生大量测量数据，造成噪声。在η个网元组成的网络中，测量k个网元间 的流量特征，需要从η个中挑出k个网元，另外，考虑到流向问题，还需考虑k个节点的排列组 合，测量方案就需要C(n，k)P化，k)。若是按照此全覆盖的测量方式和方案造成的时间复杂 度为阶乘级的，空间复杂度也很庞大。围绕着业务监测的需要出发，研究如何部署适量的探 针W满足不同的业务监测需求，W解决部署位置和部署容量的问题。
[0004] 为了解现有技术的发展状况，对已有的论文和专利进行了检索、比较和分析，筛选 出如下与本发明相关度比较高的技术信息：
[0005] 技术方案1:专利号为CN103138833A的《基于流量监测的P0N中网络编码配对关系 管理方法》专利，设及通信技术领域，主要通过Ξ步完成:第一，0LT建立起存在双向数据传 输的0NU对的网络编码连接关系，当化T检测到此0NU对的双向数据流交互后，即可开始网络 编码过程;第二，0LT基于0NU标识符统计所有存在双向数据传输的0NU对，并采用一定的算 法，将双向数据流量大小转化为对应的影响因子;第S，0LT实时监控影响因子的变化情况， 如果当未参与网络编码0NU对的影响因子IFn大于参与网络编码0NU对的影响因子I化时，贝U 拆除I巧对应的网络编码对，同时为I化对应的0NU对建立网络编码连接。
[0006] 技术方案2:专利号为CN102781014A的《基于无线传感器网络和3G网络的智能流量 监测方法》专利，设及传感器采集的流量数据与无处传感器网络信息的无缝连接技术、 802.15.4协议与TCP/IP协议之间协议转换技术。数据采集模块采集不同流体介质、管径等 动态变化的参数，采集的参数值通过异步传输方式传送至无线传感器网络的ZigBee无线通 信模块，再传输至微处理器模块进行参数的处理和运算，最后通过3G网关传输至上位机监 控中屯、，实现远距离流量监测、管理。
[0007] 技术方案3:专利号为CN103036741A的《流量监测基线的确定方法及装置》专利，设 及一种流量监测基线的确定方法及装置，在直角坐标平面内确定预设周期内的历史流量数 据图，所述直角坐标平面内的第一坐标轴表示所述预设周期内的时间，所述直角坐标平面 内的第二坐标轴表示所述历史流量数据;根据所述历史流量数据图与所述第一坐标轴和所 述第二坐标轴围成的区域，在所述坐标平面内确定基线绘制区域;在所述基线绘制区域内， 接收用户根据所述历史流量数据图触发的鼠标事件;根据所述鼠标事件在所述基线绘制区 域内的坐标位置，确定流量监测基线值。该装置包括:第一处理模块、第二处理模块、接收模 块和第Ξ处理模块。
[0008] 技术方案1能实时地根据0NU流量大小特点确定是否适合参与网络编码，从而找到 参与网络编码的最佳网络编码对，提高网络带宽的利用率，进一步减小了网络的拥塞。只是 在流量监测的基础上进行编码，并没有重点研究如何进行流量监测。技术方案2采用有线与 无线相结合的方式，节省了大量用于巡视、抄表的人力物力，提高了自动化程度管理水平， 实现了流量监测的低功耗、低成本、自动化、网络化、智能化。但是该方案的智能流量监测方 法基于无线传感器网络和3G网络，成本较高，且容易造成数据拥塞，并没有考虑优化问题。 技术方案3可W准确确定流量监测基线值，避免误报和漏报。重点在于研究流量检测极限值 的确定，并没有具体的研究流量监测的方法。
【发明内容】
[0009] 本发明正是为了克服上述缺陷而提供的一种基于顶点覆盖和弱顶点覆盖的探针 部署方法。本发明的目的在于研究基于贪屯、策略的探针部署方法，通过对最小顶点覆盖问 题的贪屯、算法进行改进，通过分支限定法的贪屯、策略实现探针部署问题。它可保证算法更 简便，耗时更短，而且使用探针数更少。
[0010] 本发明首先提出基于最小顶点覆盖的探针部署方案，实验表明，该算法能求得最 小顶点覆盖的最优解，但其计算复杂度高，花费时间长，并不能应用到大规模问题中。而且 最小顶点覆盖的最优解并不一定是网络流量监测探针部署的最优解。为此在最小顶点覆盖 的探针部署方案的基础上加 W改进，提出了基于最小弱顶点覆盖的探针部署方案，与基于 最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简单，耗时更短，是 一种更优秀的网络流量监测探针部署方案。
[0011] 本发明是通过如下技术方案来实现的：
[0012] -种基于顶点覆盖和弱顶点覆盖的探针部署方法，本发明特征在于，包括:确定测 试探针的数量及所述测试探针在网络中的部署位置。
[0013] 在基于定点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针在网络 中的部署位置的步骤为：
[0014] S1.对网络中所有节点的度排序，得到同时满足前k-1个节点的度的和小于链路数 和前k个节点的度的和大于链路数条件的k;
[0015] S2.将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无 解将k加1，重新进入S2，如果有可能有解则插入到优先队列中；
[0016] S3.若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4,如 果优先队列为空则将k加1，重新进入S2;
[0017] S4.判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入 S5；
[0018] S5.检查当前节点是否可W扩展，不能扩展的话便进入S3继续循环，如果能扩展的 话则扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后 进入S3继续循环。
[0019] 在基于最小弱顶点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针 在网络中的部署位置的步骤为：
[0020] S1.先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；
[0021 ] S2.选取一个包含的链路数目最多的节点，记为Vi;
[0022] S3.删去关联矩阵中VI对应的行及该行中值为1的元素所在的列;然后在剩下的关 联矩阵中再依次删除所有行元素之和不超过1的其他行及运些行中值为1的元素所对应的 列，直到不能再删除新的行和列为止；
[0023] S4.重复S2，S3的操作，直到所有的链路都被包含到。
[0024] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 使用最优队列和空间树来建立模型；在建立模型之后，确定测试探针的数量及所述探针在 网络模型中的部署位置。
[0025] 本发明中，使用最优队列和空间树来建立模型，包括：
[0026] 用一个优先队列维护当前可行的节点，每个节点维护着该节点情 况下还可W选择 的顶点数目ki、需要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，运些 节点按顶点的边数从大到小排序，其中对于顶点的状态，该策略中顶点有立种状态，分别为 已经选择了的状态S1，不选择的状态S2，可W选择的状态S3，其中，已经选择了的状态S1对 应解空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态si;不选择的状态 s2对应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态s2;可W选择的 状态S3对应解空间树中的父节点，选择该节点，然后设置该节点为可W选择状态s3;sl和s2 都是已经确定的状态，节点的选取只能从S3中选取。
[0027] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 建立基于最小弱顶点覆盖的检测模型；在建立模型之后，确定测试探针的数量及所述探针 在网络检测模型中的部署位置。
[0028] 本发明中，建立基于最小弱顶点覆盖的检测模型，包括：
[0029] 建立一个节点与链路的关联矩阵，该矩阵W链路为列，W节点为行，若该链路包括 该节点，则对于的值为1，否则为0。
[0030] 通过探针，实现对数据网的网络层对业务的全面监测。若是全覆盖，不仅成本高， 而且在测量时也会产生大量测量数据，造成噪声。在η个网元组成的网络中，测量k个网元间 的流量特征，需要从η个中挑出k个网元，另外，考虑到流向问题，还需考虑k个节点的排列组 合，测量方案就需要C(n，k)P化，k)。若是按照此全覆盖的测量方式和方案造成的时间复杂 度为阶乘级的，空间复杂度也很庞大。
[0031] 围绕着业务监测的需要出发，研究如何部署适量的探针W满足不同的业务监测需 求，W解决部署位置和部署容量的问题。要求解决的部署实例为"某数据网拓扑图"。
[0032] 1.假设问题中的数据网内的链路权值都相等，假设为1;
[0033] 2.假设问题中网元间的通信路由规则采用最短路算法；
[0034] 3.在最小弱顶点覆盖模型中，假设一个网元可W监测与其直接相关的所有链路的 流量，且满足流量守恒；
[0035] 4.在最小集合覆盖模型中，假设任意两网元可W通过通信监测其路径上的所有链 路的状态，网络监测命令发生在探针与探针之间；
[0036] 5.由于网络边缘节点的度数通常较小，若把探测站点的位置选定在网络的边缘 处，那么从该探测站点发送出的探测的数目W及探测的能力就会收到相应的限制，因而假 设探针位置不会在网络的边缘。
[0037] 针对网络流量监测的业务需求，可W使用化tFlow的探测方式。在网络中某一节点 设置探针可W得到与运一节点相联的所有链路上的流量；因此，为了得到网络中所有链路 的网络流量，一般可W通过在某些交换节点（路由器)配置监测器实现，我们要考虑的问题 是:在网络哪些节点上设置监测器，才能使得在可W得到每一条链路流量的条件下，所需流 量监测器数目最小。
[0038] 使用最小顶点覆盖可W解决运一问题。顶点覆盖问题已被证明是NP完全的，只能 用近似算法算出近似最优解。我们本文中对最小顶点覆盖问题的贪屯、算法进行改进，通过 分支限定法的贪屯、策略实现探针部署问题。
[0039] 在考虑到网络监测方式的同时，加上流量守恒的约束，使用最小弱顶点覆盖能够 部署更少的探针来实现整个网络的网络流量监测。同样最小弱顶点覆盖问题也已被证明是 NP完全的，也是只能使用近似算法求近似最优解。我们运里使用贪屯、策略来实现探针部署 问题。
[0040] 对于流量监测测试的评估指标：
[0041] 1.部署的探针的个数；
[0042] 2.链路覆盖率。
[0043] 我们需要把需要部署探针的网络图转化为无向图G(V，E)，其中ν=(νι，ν2，···，νη) 为网络节点集(在IP网络中可看作为路由器），E=(el，e2，…，em)为网络中的链路集合。其 中，n= |V|，m= |E|分别表示G中节点和链路的数目。用ek=(vi，vj)表示ek是连接节点Vi和vj 的一条链路。
[0044] 用De gr e e (V)表示节点V的链路数，即节点V的度。
[0045] 把原始网络图的所有路由器，交换机等设备按照1，2,……的顺序标号，然后统计 所有的链路信息，将该图转化为无向图。该网络有160个节点，185条链路。是一个稀疏图（边 的条数m远小于η 2的图），可W用邻接链表来表示无向图，但是考虑一般情况，为了能够解决 各种的图，使用邻接矩阵来表示无向图。
[0046] 首先介绍基于最小顶点覆盖的探针部署方案：
[0047] 根据下面定义，可W很方便的描述问题模型
[004引定义1:给定无向图G(V，E)，其中V是顶点集，Ε是边集，S是V的子集，若根据与S中顶 点相关联的各条边的流量，可W确定E中任意边的流量，则称S是图G关于流量的测量集。
[0049] 有效测量问题的目标就是求给定图G关于流量的最小测量集。可W转换为求定义2 中图G的最小顶点覆盖问题。
[0050] 定义2(最小顶点覆盖问题）：指给定一个无向图G(V，E)，求顶点集V的一个最小子 集S，使得e = (u，v)eE，且ueS或veS，即E中的任一边至少含有此子集中的一个点作为顶 点，也就是说S中的顶点覆盖了边集E。
[0051] 其数学描述为：
[0化2] min CX其中xiES
[0化3]
[0054] 其中c=[l，l，···，υ和X=[X1，X2，···，XrJ都是长为η的向量，（aij)nXn是图的邻接矩 阵，且
[0化5]
2
[0056] 最小顶点覆盖问题已被证明是NP完全的，到目前为止还不存在多项式时间算法来 求解，我们可W用贪屯、算法去求出近似最优解，即每次迭代都选取度最大的节点作为探针， 然后所有与其相连的节点都可W排除掉，满足每次选取探针都是当下情况的最优情况，但 是考虑到每次的最优并不一定能得到整体上的最优，为了找到更小的解，通过下面的限定 策略，我们对贪屯、进行改进，通过分支界限法来得到更优解。
[0057] 对所有节点的度从大到小排序，取前k个节点，满足
[0化引
.3.
[0059] 时，是可能满足顶点覆盖的界限。
[0060] 通过上述约束，我们在使用贪屯、算法之前，先求出一个最小可能的最优解k，将问 题转化为判定无向图中是否存在k个节点满足最小顶点覆盖。通过贪屯、策略和限定策略去 判定，若满足则k是最优解，若不满足则将k加1，继续判定。
[0061 ]在介绍具体的判定过程之前，首先使用最优队列和空间树来建立模型，用一个优 先队列维护当前可行的节点，每个节点维护着该节点情况下还可W选择的顶点数目ki、需 要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，运些节点的排序遵循贪 屯、策略，按顶点的边数从大到小排序。对于顶点的状态。该策略中顶点有Ξ种状态，分别为 已经选择了的状态S1，不选择的状态S2,可W选择的状态S3。其中，已经选择了的状态S1对 应解空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态S1;不选择的状态 S2对应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态S2。可W选择的 状态S3对应解空间树中的父节点，选择该节点，然后设置该节点为可W选择 状态S3"S1和S2 都是已经确定的状态，节点的选取只能从S3中选取。
[0062] 取出最优队列里的第一个节点进行扩展：
[0063] 将该节点设置为S1，同时按照公式4修改该节点的信息，然后把该节点放入空间树 的左节点;再将该节点设置为S2,不用修改其他节点信息直接放入空间树的右节点。
[0064] ki = ki-l, e = e-De邑ree ,De邑ree = 0 4
[00化]通过约束条巧
先对右节点判定，若满足，将该点插入最优队列； 再选取左节点进行判定，若满足，将该节点插入最优队列。
[0066] 对上面步骤的迭代就是具体的判定过程。
[0067] 相应的流程图如图1所示。
[0068] 在基于最小顶点覆盖的探针部署算法的基础上加 W改进，提出了基于最小弱顶点 覆盖的探针部署算法：
[0069] 在定义1的基础上，由于探针设置在路由器或交换机等交换设备上，根据流量守 恒，那么图G还满足W下两条约束条件：
[0070] 1.对图G的顶点集V中的任意顶点V，其度Degree(v) > 2;
[0071] 2.对图G的顶点集V中的任意顶点V，满足流守恒方程，即流进=流出。
[0072] 尽管W下原因会将导致流守恒方程的失真，如:交换设备是数据的源或汇，而不仅 仅是数据转发器;多播导致输出端口的数据复制;交换设备本身的数据包延迟或丢失。但是 若干研究表明，流守恒方程所具有的相对误差小于0.05%。
[0073] 定义3(弱顶点覆盖）：假定无向图G(V，E)目满足对任意veV有Degree(v) >2,称 《cr是图G的弱顶点覆盖集，当且仅当执行W下操作能使E中所有的边都可W被标记：
[0074] (1)标记所有与S中顶点相关联的边；
[0075] (2)若某个顶点V的Degree(v)-1条相关联的边己被标记，则标记剩下的那条相关 联的边；
[0076] (3)重复第(2)步，直到不能再标记新的边为止。
[0077] 显然，由此弱顶点覆盖S就可W得到图G中各链路的流量。本文利用关联矩阵的概 念建立求解弱顶点覆盖问题的模型，为此先给出W下定义。
[007引定义4(关联关系)在无向图G(V，E)中，若vEV是eEE的顶点之一，贝嚇V与e之间存 在着关联关系，记为vRe
[0079] 定义5(关联矩阵）图G(V，E)的关联矩阵A=(au)是
[0080] 指如下定义的η Xm矩阵：
[0081]
3
[0082] 根据关联矩阵的定义，可知V的一个子集构成图G的一个覆盖，当且仅当在它包含 的节点所对应的关联矩阵的行中每列至少存在一个1。
[0083] 根据W上分析，采用贪屯、算法可W求解弱顶点覆盖问题，需要注意的是我们的网 络图中的边界点度为1，并不满足条件约束1，所W我们需要对无向图进行预处理。
[0084] 对于初始情况下度为1的顶点VI，只有一个边与该点存在关联，该边记为ej响的另 一个顶点记为Vj。
[0085] 当vj只有一个度为1的邻顶点VI，只要得出vj其他相关边的流量信息就能根据流量 算出eu的流量。即vj满足最小弱顶点覆盖，只是计算该边的度需要把eu加上;或者vj是探针 部署位置时也直接能监测到eu的流量。
[0086] 当vj有多化|k>l)个度为1的邻顶点，若不把节点V六受为探针，则至少需要设置k个 探针，所W只有将节点Vj设为探针，才能保证部署探针目数最少。
[0087] 根据上面分析，可知初始情况度为1的节点可W都不设探针，可W直接被舍弃，但 预处理舍弃一个度为1的节点时，不将其他与其相连的节点的度减1。
[0088] 鉴于上述基于最小弱顶点覆盖的流量监测模型，设计其算法流程如下：
[0089] Stepl:先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；
[0090] Step2:选取一个包含的链路数目最多的节点，记为VI;
[0091] Step3:删去关联矩阵中Vi对应的行及该行中值为1的元素所在的列；然后在剩下 的关联矩阵中再依次删除所有行元素之和不超过1的其他行及运些行中值为1的元素所对 应的列，直到不能再删除新的行和列为止；
[0092] Step4:重复Step2，Step3的操作，直到所有的链路都被包含到。
[0093] 相应的算法流程图如图2所示。
[0094] 本发明的技术关键点在于：
[00M] 1、本算法对最小顶点覆盖问题的贪屯、算法进行改进，通过分支限定法的贪屯、策略 实现探针部署问题；
[0096] 2、在考虑到网络监测方式的同时，加上流量守恒的约束，使用最小弱顶点覆盖能 够部署更少的探针来实现整个网络的网络流量监测。
[0097] 本发明的有益效果：本专利提出一种基于顶点覆盖和弱顶点覆盖的探针部署技 术，其优点在于，该技术立足于对最小顶点覆盖问题的贪屯、算法，在该算法的基础上加 W改 进，提出了基于顶点覆盖和弱顶点覆盖的探针部署算法。首先使用最小顶点覆盖，使得在可 W得到每一条链路流量的条件下，所需流量监测器数目最小。之后改进为最小弱顶点覆盖。 仿真表明，与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简 单，耗时更短，是一种更优秀的网络流量监测探针部署方案。
【附图说明】
[0098] 图1为基于最小顶点覆盖的探针部署算法流程图；
[0099] 图2为基于最小弱顶点覆盖的算法流程图。
【具体实施方式】
[0100] -种基于顶点覆盖和弱顶点覆盖的探针部署方法，本发明特征在于，包括:确定测 试探针的数量及所述测试探针在网络中的部署位置。
[0101] 在基于定点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针在网络 中的部署位置的步骤为：
[0102] S1.对网络中所有节点的度排序，得到同时满足前k-1个节点的度的和小于链路数 和前k个节点的度的和大于链路数条件的k;
[0103] S2.将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无 解将k加1，重新进入S2，如果有可能有解则插入到优先队列中；
[0104] S3.若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4,如 果优先队列为空则将k加1，重新进入S2;
[0105] S4.判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入 S5；
[0106] S5.检查当前节点是否可W扩展，不能扩展的话便进入S3继续循环，如果能扩展的 话则扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后 进入S3继续循环。
[0107] 在基于最小弱顶点覆盖的探针部署方法中，确定测试探针的数量及所述测试探针 在网络中的部署位置的步骤为：
[0108] S1.先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；
[0109] S2.选取一个包含的链路数目最多的节点，记为Vi;
[0110] S3.删去关联矩阵中VI对应的行及该行中值为1的元素所在的列;然后在剩下的关 联矩阵中再依次删除所有行元素之和不超过1的其他行及运些行中值为1的元素 所对应的 列，直到不能再删除新的行和列为止；
[0111] S4.重复S2, S3的操作，直到所有的链路都被包含到。
[0112] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 使用最优队列和空间树来建立模型；在建立模型之后，确定测试探针的数量及所述探针在 网络模型中的部署位置。
[0113] 本发明中，使用最优队列和空间树来建立模型，包括：
[0114] 用一个优先队列维护当前可行的节点，每个节点维护着该节点情况下还可W选择 的顶点数目ki、需要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，运些 节点按顶点的边数从大到小排序，其中对于顶点的状态，该策略中顶点有立种状态，分别为 已经选择了的状态S1，不选择的状态S2，可W选择的状态S3，其中，已经选择了的状态S1对 应解空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态si;不选择的状态 s2对应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态s2;可W选择的 状态S3对应解空间树中的父节点，选择该节点，然后设置该节点为可W选择状态s3;sl和s2 都是已经确定的状态，节点的选取只能从S3中选取。
[0115] 在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 建立基于最小弱顶点覆盖的检测模型；在建立模型之后，确定测试探针的数量及所述探针 在网络检测模型中的部署位置。
[0116] 本发明中，建立基于最小弱顶点覆盖的检测模型，包括：
[0117] 建立一个节点与链路的关联矩阵，该矩阵W链路为列，W节点为行，若该链路包括 该节点，则对于的值为1，否则为0。
[0118] 如表1所示，通过使用分支限定法的最小顶点覆盖模型部署该网络，只需部署43个 探针就能够实现流量监控网络覆盖率100%，即基于最小顶点覆盖的探针部署方案部署43 个探针就可W实现该网络图全图各条边的流量监测。
[0119] 表1评价指标 「01201
[0121] 需要指出的是，尽管分支限定法能求得最小顶点覆盖的最优解，但其计算复杂度 高，花费时间长，并不能应用到大规模问题中。而且最小顶点覆盖的最优解并不一定是网络 流量监测探针部署的最优解，所W为了找到算法更简便，耗时更短，而且使用探针数更少的 部署方案，下面将结合网络流量守恒的性质通过最小弱顶点覆盖来部署探针。
[0122] 如表2所示，通过使用最小弱定点覆盖的方法，只需部署32个探针就能够实现流量 监控网络覆盖率100%。在该种方法中，有部分路径的网络流量是通过流量守恒计算得到 的。
[0123] 表2评价指标
[0124]
[0125] 与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简 单，耗时更短，是一种更优秀的网络流量监测探针部署方案。
[0126] 但是运两种探针部署防案都是被动测试，能够利用端口镜像，多路转发W用链路 串接等方式收集网络中本身传输的数据包，包括业务数据包、信令数据包和管理信息数据 包等，分析网络性能，被动地监测网络性能，有着不增加额外流量，对网络影响很小的优点。
【主权项】
1. 一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在于，包括:确定测试探针 的数量及所述测试探针在网络中的部署位置;其中， 确定测试探针的数量及所述测试探针在网络中的部署位置的步骤为：51. 对网络中所有节点的度排序，得到同时满足前k-1个节点的度的和小于链路数和前 k个节点的度的和大于链路数条件的k;52. 将原图数据构造成一个解空间树的节点，利用定界策略判断是否有解，如果无解将 k加1，重新进入S2，如果有可能有解则插入到优先队列中；53. 若优先队列不为空，那么便从优先队列中取出第一个可行的节点，进入S4,如果优 先队列为空则将k加1，重新进入S2;54. 判断当前节点是否满足解的条件，如果满足便输出解退出，如果不满足便进入S5;55. 检查当前节点是否可以扩展，不能扩展的话便进入S3继续循环，如果能扩展的话则 扩展，然后验证扩展到左右节点是否有解，将有解的扩展节点插入到优先队列中，然后进入 S3继续循环； 确定测试探针的数量及所述测试探针在网络中的部署位置的步骤为：51. 先删除所有度为1的节点，即删除关联矩阵中所有行元素之和为1的行；52. 选取一个包含的链路数目最多的节点，记为Vi;53. 删去关联矩阵中^对应的行及该行中值为1的元素所在的列;然后在剩下的关联矩 阵中再依次删除所有行元素之和不超过1的其他行及这些行中值为1的元素所对应的列，直 到不能再删除新的行和列为止；54. 重复S2，S3的操作，直到所有的链路都被包含到。2. 根据权利要求1所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在 于，在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 使用最优队列和空间树来建立模型； 在建立模型之后，确定测试探针的数量及所述探针在网络模型中的部署位置。3. 根据权利要求2所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在 于，使用最优队列和空间树来建立模型，包括： 用一个优先队列维护当前可行的节点，每个节点维护着该节点情况下还可以选择的顶 点数目ki、需要覆盖的剩余边数e、顶点的状态state、顶点的边数Degree等信息，这些节点 按顶点的边数从大到小排序，其中对于顶点的状态，该策略中顶点有三种状态，分别为已经 选择了的状态si，不选择的状态s2,可以选择的状态S3,其中，已经选择了的状态si对应解 空间树数中的左节点，选择该节点，然后设置该节点为已经选择状态si;不选择的状态s2对 应解空间树中的右节点，不选择该节点，然后设置该节点为不选择状态s2;可以选择的状态 S3对应解空间树中的父节点，选择该节点，然后设置该节点为可以选择状态s3;sl和s2都是 已经确定的状态，节点的选取只能从S3中选取。4. 根据权利要求1或2或3所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其 特征在于，在确定测试探针的数量及所述探针在网络中的部署位置之前，所述方法还包括： 建立基于最小弱顶点覆盖的检测模型； 在建立模型之后，确定测试探针的数量及所述探针在网络检测模型中的部署位置。5. 根据权利要求4所述的一种基于顶点覆盖和弱顶点覆盖的探针部署方法，其特征在
【专利摘要】本发明涉及一种基于顶点覆盖和弱顶点覆盖的探针部署方法，包括：确定测试探针的数量及所述测试探针在网络中的部署位置。本发明提出一种基于顶点覆盖和弱顶点覆盖的探针部署技术，其优点在于，该技术立足于对最小顶点覆盖问题的贪心算法，在该算法的基础上加以改进，提出了基于顶点覆盖和弱顶点覆盖的探针部署算法。首先使用最小顶点覆盖，使得在可以得到每一条链路流量的条件下，所需流量监测器数目最小。之后改进为最小弱顶点覆盖。仿真表明，与基于最小顶点覆盖的部署方案相比，本方案使用的探针数更少，而且算法更简单，耗时更短，是一种更优秀的网络流量监测探针部署方案。
【IPC分类】H04L12/24, H04L12/26
【公开号】CN105490834
【申请号】CN201510807537
【发明人】刘宇明, 田丰, 刘彤, 何林宏, 李辉, 苏进, 李晓耕, 李朝广, 韩熙媛
【申请人】云南电力调度控制中心
【公开日】2016年4月13日
【申请日】2015年11月19日
最新回复(0)