基于复杂网络的互联网拓扑探测节点优化部署方法

摘要

本发明公开一种基于复杂网络的互联网拓扑探测节点优化部署方法，应用于网络探测领域，利用网络拓扑的无度性、自相似性等复杂网络特征，根据已知的部分拓扑的度分布信息，对全局拓扑的度分布信息做出估计；然后根据估计的度分布信息随机生成整体拓扑；利用最小相对显著性将选择的范围缩小至相对显著性最小的边的关联节点集合，再选择其中覆盖当前剩余边数最多的节点，快速缩小问题规模，迅速选择出部署节点。

说明书

技术领域

本发明属于网络探测领域，特别涉及一种网络拓扑探测节点部署技术。

背景技术

传统的网络拓扑识别方法依赖于网络内部节点的协作，需要从网络内部的非控制节点处获取网络拓扑的相关信息。根据获取信息时使用的网络协议的不同，传统网络拓扑识别的方法包含基于路由协议的方法、基于简单网络管理协议SNMP的方法、基于互联网控制消息协议ICMP的方法等三类。

在进行网络拓扑识别时，需要在网络中部署探测节点来获取必要的数据。在实际的网络拓扑识别过程中，探测节点的部署和维护通常会消耗较大的成本，无法大量的部署节点。如何将有限数目的探测节点部署在网络中的适当位置，使得可探测到的网络拓扑范围尽可能大，是一个有意义的研究课题。

目前，针对网络性能参数探测的网络探测节点部署研究较多，而针对网络拓扑识别的探测节点部署的研究则很少。针对网络性能探测的探测节点部署研究是在假设网络拓扑结构完全已知的情况下分析节点部署，而在实际网络拓扑识别过程中，网络拓扑结构完全已知的条件无法满足。所以，本发明提出在网络拓扑结构部分已知时估计整体拓扑的方法，并基于最小相对显著性原则选取部署节点，形成在网络拓扑部分已知条件下的探测节点部署方案。

文献“E.Gregori,A.Improta,L.Lenzini,et al.On the incompleteness of theAS-level graph:a nov-el methodology for BGP route collector placement[M].2012,253–264”研究了基于BGP的AS级拓扑识别中BGP报文收集节点的部署问题。研究的具体问题是：在网络中寻找最小的部署节点集合，并满足网络上其他节点经过有限的P2C连接可达集合中的某个部署节点的条件。文献[13]将该问题抽象成一个待条件约束的MSC问题，并给出了一种贪婪算法。但在实际拓扑识别的过程中无法满足拓扑已知的条件，所以该方法难以被运用于实际拓扑识别中。

文献“W.Han,K.Xu.A method for placing traceroute-like topologydiscovery instrumentation[M].2008,1160–1164”提出了一种基于Traceroute探测的节点部署方法。文章认为单个探测节点的Traceroute的结果可看成网络拓扑从源节点出发的最短路径树，该树是拓扑的广度优先的生成树，未探测到的链路有一部分属于同一层的两个节点之间的连接，另一部分属于已知路径的等价最短路径。该文设计了一种启发式贪婪探测部署算法。启发式的算法在实际探测时具有可行性，这是该类方法相对于假设网络拓扑已知的方法的优势。但是该类方法的效果通常会比假设网络拓扑已知的方法略差，因为其缺少全局拓扑的信息。

发明内容

为解决上述技术问题，本申请提出了一种基于复杂网络的互联网拓扑探测节点优化部署方法，在只有部分拓扑已知的条件下，使用基于部分拓扑生成整体拓扑随机模型的方法来根据部分拓扑生成整体拓扑。

本申请采用的技术方案为：基于复杂网络的互联网拓扑探测节点优化部署方法，包括：

S1、利用输入的部分拓扑对整体拓扑的度互补累积概率分布进行估计；

S2、根据估计的互补累积概率分布生成随机拓扑；

S3、基于最小相对显著性优先原则选择当前随机拓扑下的部署节点；并记录选择的部署节点；

S4、判断生成随机拓扑次数是否已经达到设定的数目，如果没有达到要求，则转至步骤S2；否则执行步骤S5。

S5、从记录中选择出现次数最多的Max个节点，作为最终的部署节点；

其中，Max为部署节点个数上限。

进一步地，所述步骤S1具体为：

S11、统计输入的部分拓扑中度值大于0的节点的度概率分布率；

S12、根据步骤S11得到的各节点的度概率分布率计算得到互补累积概率函数；

S13、对步骤S12得到的互补累积概率函数进行双对数坐标变换；

S14、对经步骤S13双对数坐标变换后得到的函数采用线性回归方法进行线性拟合，得到对应的拟合系数，从而得到估计的互补累积概率分布。

进一步地，所述步骤S2具体为：

S21、将所有节点分为拓扑已知节点集合与拓扑未知节点集合；

S22、根据步骤S1估计的拓扑度互补累积概率分布，对从拓扑未知节点集合中选取的节点进行拓扑生成。

更进一步地，所述步骤S22包括以下分步骤：

A1、从拓扑未知节点集合中选取一个节点，对该节点生成一个0到1之间的随机数，根据随机数估计该节点的出度；

A2、若该节点的出度对应的待连接的节点属于拓扑已知节点集合，则以第一概率从拓扑已知节点集合中选取待连接节点；

若该节点的出度对应的待连接的节点属于拓扑未知节点集合，则以第二概率从拓扑未知节点集合中选取待连接节点。

更进一步地，所述第一概率为：

其中，k_u表示节点u当前的度，u表示待连接的节点，V₁表示拓扑已知节点集合。

更进一步地，所述第二概率为：

其中，V₂表示拓扑未知节点集合。

进一步地，所述步骤S3具体为：

S31、计算随机拓扑所有可部署节点的SPT可覆盖的边；

S32、计算当前仍未被覆盖的边在当前仍未被选中的可部署节点集合上的相对显著性，并选择相对显著性最小的一条边；

S33、对所选择的边的关联节点集合中的每个节点，计算其能覆盖到剩余边的条数，并选择可覆盖边数最多的一个节点作为部署节点，然后从关联节点集合中移除该节点，以及将该节点的SPT可覆盖的边从当前仍未被覆盖的边集中移除；

S34、重复步骤S32至步骤S33直至所有边都被覆盖。

本发明的有益效果：基于复杂网络的互联网拓扑探测节点优化部署方法，在只有部分拓扑已知的条件下，使用基于部分拓扑生成整体拓扑随机模型的方法来根据部分拓扑生成整体拓扑，使用基于最小相对显著性优先的探测节点部署方法来根据生成的拓扑寻找部署节点；具有以下优点：

1)能够有效地根据部分拓扑生成可以较为准确反映拓扑特征的整体拓扑。

2)在以路由器级网络拓扑特征为基础的拓扑生成模型中的结果，在大部分情况下要优于“集合覆盖贪婪算法”；两算法的差别在于每次部署节点的选取范围不同，“基于最小相对显著性优先的探测节点部署算法”的节点选取范围普遍要小于“集合覆盖贪婪算法”。

附图说明

图1为本申请的方案流程图；

图2为双对数坐标下节点度的互补累积概率分布拟合系数获取流程；

图3为基于部分拓扑度概率分布的拓扑生成方法流程图；

图4为基于最小相对显著性优先的探测节点部署算法流程。

具体实施方式

为便于本领域技术人员理解本发明的技术内容，下面结合附图对本发明内容进一步阐释。

如图1所示为本申请的方案流程图，本申请的技术方案为：基于复杂网络的互联网拓扑探测节点优化部署方法，包括：

S1、利用输入的部分拓扑对整体拓扑的度互补累积概率分布进行估计；

S2、根据步骤S1估计的互补累积概率分布生成随机拓扑；

S3、基于最小相对显著性优先原则选择当前随机拓扑下的部署节点；并记录选择的部署节点；

S4、判断生成随机拓扑并选择探测节点部署的次数是否已经达到设定的数目，如果没有达到要求，则转至步骤S2；否则执行步骤S5。具体的设定数目需要根据实际的拓扑规模，拥有的计算能力，允许的计算时间等实际情况做出折衷的考虑.

S5、从记录中选择出现次数最多的Max个点，作为最终的部署节点；

其中，Max为部署节点个数上限，Max的值是人为指定部署节点个数上限。该上限值的设置，也相当于对节点部署成本的限制。

如图2所示，步骤S1具体为：在网络拓扑G(V,E)中，节点分布在度值较小的区间内出现较为密集，但在度值较大的区间内很稀疏，大部分度值上不存在节点，即出现概率为0。为了减小由于该情况造成的影响，可考虑将节点度的概率分布转换为对应的互补累积分布进行平滑处理。为了便于拟合，先将互补累积概率分布函数进行对数化表示再进行拟合。包括以下步骤：

S11、统计输入的部分拓扑中度值大于0的节点的度概率分布率P(k)，k＝1,2，...，d_max；d_max为局部拓扑的最大度值；

S12、根据步骤S11得到的各节点的度概率分布率计算得到互补累积概率函数；

S13、对步骤S12得到的互补累积概率函数进行双对数坐标变换；令x(k)＝lnk,y(k)＝lnF(k)，记y(k)＝F_ln(x(k))；

S14、对经步骤S13双对数坐标变换后得到的函数F_ln(x(k))采用线性回归方法进行线性拟合，得到对应的拟合系数。具体为：F_ln(x(k))的线性拟合函数为：得到线性拟合系数a，b；并且根据a，b计算幂律分布，得到局部拓扑的互补累积度概率分布拟合：将作为整体拓扑的互补累积概率分布的估计。

如图3所示，步骤S2具体为：

S21、将所有节点分为拓扑已知节点集合V₁与拓扑未知节点集合V₂；

S22、根据步骤S1估计的拓扑度互补累积概率分布对从拓扑未知节点集合中选取的节点进行拓扑生成；

对选取出的节点v，生成一个0到1之间的随机数r，按如下公式计算出v的出度m(r)：

其中

为节点v的度的估计值，其中a,b为上一节中得到的拟合系数；

确定节点v的每一个待连接的节点所属的集合：令v的一条边的连接节点在V₁中，当m(r)大于1时，令剩余的每一条边皆以概率p与V₁中的节点相连，以概率1-p与V₂中的节点相连，其中p为：

确定节点v的所有待连接节点：若节点v待连接的节点u属于V₁，则节点u从V₁中以概率p₁(u)选取：

其中，k_u表示节点u当前的度。若节点v待连接的节点u属于V₂，则节点u从V₂中以概率p₂选取：

为了避免出现重边，当节点v与节点u之间已有边相连时，需重新选择连接节点。

当集合V₂中所有的节点都进行了拓扑生成时，则生成了整体估计拓扑。

步骤S3中相对显著性作如下定义：

关联节点集合s(e,N)：在拓扑G(V,E)上，属于可部署节点的集合N且其对应的SPT可覆盖到边e的节点集合，其中，N包含于V。SPT表示最短路径树(Shortest-path Tree,SPT)，是图的一种生成树，且在该图的所有生成树中，SPT上从根节点到其他任意一个节点的路径都是最短路径。

相对显著性s(e,N)：在拓扑G(V,E)上，N中的每一个节点对应的SPT集合中，可覆盖到边e的SPT的个数，其中，N包含于V，即边e的相对显著性为其关联节点集合中的元素个数：

s(e,N)＝|S(e,N)|＝|{v∈N|e∈T_v(G)}|

如图4所示包括以下分步骤：

S31、计算随机拓扑所有可部署节点的SPT可覆盖的边；

S32、计算当前仍未被覆盖的边在当前仍未被选中的可部署节点集合上的相对显著性，并选择相对显著性最小的一条边；

将节点的选择范围由全体可部署节点集合缩小至相对显著性最小的边的关联节点集合中，减少了在大量可覆盖边数相同的节点中进行随机选择的可能性；

S33、对所选择的边的关联节点集合中的每个节点，计算其能覆盖到剩余边的条数，并选择可覆盖边数最多的一个节点作为部署节点，然后从关联节点集合中移除该节点，以及将该节点的SPT可覆盖的边从当前仍未被覆盖的边集中移除；通过从确定的节点集合中选取覆盖当前剩余边最多的节点，将快速缩小问题的规模。

S34、重复步骤S32至步骤S33直至所有边都被覆盖。

本身的方法生成拓扑的度分布幂指数的均值与原拓扑接近，生成的拓扑与原拓扑的度分布上较为一致，具有相近的无标度特性。生成拓扑的直径和平均路径长度与拓扑中节点数的对数在一个数量级，可认为所生成的拓扑具有与原拓扑相近的部分小世界特性。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的权利要求范围之内。