基于非参数假设检验的拓扑推断算法.pdf

《基于非参数假设检验的拓扑推断算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第43卷第5期电子科技大学学报V_0I．43No．52014芷9)9JournalofUniversityofElectronicScienceandTechnologyofChinaSep．2014基于非参数假设检验的拓扑推断算法张润生，康一丁2，张冠杰，李艳斌(I．中国电子科技集团公司第五十四研究所石家庄050081；2．空军航空大学信息对抗系长春130022)【摘要】针对基于门限比较的二叉树修剪拓扑推断算法稳健性差的问题，提出了一种基于非参数假设检验的网络拓扑推断算法。该算法首先应用经典的二又树拓扑推断算法获得树状网络的二叉树结构

2、，然后应用维尔科克森秩和检验算法逐个判断二叉树中的每条内部链路是否需要修剪，最后修剪二叉树，删除所有需要修剪的内部链路，得到真实的树状拓扑。由于该算法使用统计检测的方法，无需设置门限，相对门限比较法具有更好的稳健性。仿真实验表明，该算法相比基于门限的二叉树修剪算法具有更高的推断精度．关键词二叉树修剪：网络层析成像：拓扑推断：维尔科克森秩和检验中图分类号TP393文献标志码Adoi：10．39690．issn．1001．0548．2014．05．023TopologyInferenceAlgorithmBasedonNonparametr

3、icHypothesisTestZHANGRun．sheng，KANGYi．ding2，ZHANGGuan-jie。，andLIYan-bin(1．The54ResearchInstituteofChinaElectronicTechnologyGroupCorporationShijiazhuang050081；2．AviationUniversityofAirForceChangchun130022)AbstractInordertoimprovetherobus缸lessofbinarytreepruningbasedtopolo

4、gyinferencealgorithm．atopologyinferencealgorithmbasedonnonparametrichypothesistestiSproposed．Inthismethod．thebinarytreeiSobtainedbvusiIlgclassicalbinarytreeinferencealgorithm；wilcoxonranksumtestmethodiSappliedtotestwhichinternalnodesshouldberemoved；andfinallyalltheintema

5、lnodeswhichshouldberemovedaredeletedtogeneratetherealtopology．SimulationresultsshowthatthealgorithmCangethighertopologyinferenceaccuracythanthemethodbasedonthresholdcomparison．Keywordsbinarytreepruning；networktomography；topologyinference；wilcoxonranksumtest拓扑推断对于网络管理和网络协

6、议优化等都具delay-variancetree)推断出二叉树结构，然后通过设有十分重要的意义。近年来出于安全的考虑，许多置固定的门限修剪掉长度较小的链路，获得真实拓网络设备的安全设置日益严格，从外部通过当前的扑，但该算法中不同门限对算法的性能影响很大，测量方法很难获得网内的拓扑结构[1-2]。因此，文献且目前没有一种选择最佳门限的方法。文献【5】提出【2．3】提出了基于网络层析成像的拓扑推断技术，其了两种树状拓扑推断算法，基于惩罚最大似然基本思想是由源节点向目标节点发送数据包测量目(maximumpenal~edlikelihoodt

7、ree，MPLT)拓扑推断标节点之间的相关性，然后通过统计推断的方法获方法和自底向上分层聚类(agglomerativelikelihood得以源节点为根节点，以目标节点为叶子节点的逻tree，ALT)的拓扑推断方法，前者通过构建最大似然辑树状拓扑。模型推断拓扑，可以获得不错的推断精度，但需要根据测量节点相关性的方法不同，网络层次成凭经验设置惩罚因子，且其运算量很大；后者通过像拓扑推断算法可以分为两类，基于多播的拓扑推最大似然估计叶子节点相关性，对叶子节点自底向断技术和基于单播的拓扑推断技术12]，但两类算法上分层聚类获得二叉树，然后同

8、文献【4】一样设置门在推断网络拓扑时所用的统计推断技术是通用的。限修剪二叉树。文献【6．7】分别提出了高效的拓扑推文献【4】提出了基于门限比较二叉树修剪的拓扑推断断算法，可以减少测量叶子节点相关性所需发送的