利用有限混合模型的高效网络拓扑推断算法

doi:10.3969/j.issn.1001-2400.2015.04.022

J4 ›› 2015, Vol. 42 ›› Issue (4): 133-139.doi: 10.3969/j.issn.1001-2400.2015.04.022

利用有限混合模型的高效网络拓扑推断算法

张润生1;刘健2;李艳斌1

(1. 中国电子科技集团公司第五十四研究所，河北石家庄 050081；
2. 中国空间技术研究院通信卫星事业部，北京 100094)

收稿日期:2014-03-14 出版日期:2015-08-20 发布日期:2015-10-12
通讯作者: 张润生
作者简介:张润生(1984-)，男，中国电子科技集团公司第五十四研究所博士研究生，E-mail: zhang_runsheng@163.com．
基金资助:
国家科技支撑计划资助项目(2011BAH24B04)，中国博士后科学基金面上资助项目(20110490989)

Efficient topology inference algorithm using the finite mixture model

ZHANG Runsheng1;LIU Jian2;LI Yanbin1

(1. The 54th Research Institute of CETC, Shijiazhuang 050081, China;
2. The Telecommunication Satellite Institute of China Academy of Space Technology, Beijing 100094, China)

Received:2014-03-14 Online:2015-08-20 Published:2015-10-12
Contact: ZHANG Runsheng

摘要/Abstract

摘要：

针对现有高效网络拓扑推断算法的性能对设定门限值非常敏感的问题，提出了利用有限混合模型的高效层析成像网络拓扑推断算法．该算法首先从叶子节点集合中任选一个节点，测量该节点与其余节点的相关性集合，然后对测量数据建立有限混合模型，对叶子节点进行粗略分类，推断出相应的内部节点; 接下来对粗略分类结果中的每一个节点类重复上述过程，如此迭代直至推断出所有内部节点为止．试验结果表明，该算法可达到现有算法取最优门限时的拓扑推断精度，且该算法与现有的高效层析成像拓扑推断算法相比，只需测量更少的节点相关性数据．

关键词: 拓扑推断, 网络层析成像, 有限混合模型

Abstract:

The performance of the existing efficient topology inference algorithm is highly sensitive to the threshold. To address the problem, a finite mixture model based topology inference algorithm is proposed. Firstly, a leaf node is selected from the original leaf-node set, and then the similarities between the node and the other leaf nodes are measured, after which the original leaf-node set is roughly divided into several subsets using the finite mixture model based on the measured similarities. The internal nodes corresponding to each subset could be inferred afterwards. Subsequently, the above procedures are applied for each subset obtained from rough division, and the process is iterated until all of the internal nodes are found. Analysis and simulation show that the proposed algorithm needs less correlation data than the existing algorithm, and performs almost as well as the existing algorithm with the optimum threshold.

Key words: topology inference, network tomography, finite mixture model

张润生;刘健;李艳斌. 利用有限混合模型的高效网络拓扑推断算法[J]. J4, 2015, 42(4): 133-139.

ZHANG Runsheng;LIU Jian;LI Yanbin. Efficient topology inference algorithm using the finite mixture model[J]. J4, 2015, 42(4): 133-139.

参考文献

［1］ Zhang X, Phillips C. A Survey on Selective Routing Topology Inference through Active Probing［J］. IEEE Communications Surveys and Tutorials, 2012, 14(4): 1129-1141.
［2］张润生, 李艳斌, 李啸天. 基于合并分层聚类的网络拓扑推断算法［J］. 电子学报, 2013, 41(12): 2346-2352.
Zhang Runsheng, Li Yanbin, Li Xiaotian. Agglomerative Hierarchical Clustering Based Algorithm for Network Topology Inference ［J］. Acta Electronica Sinica, 2013, 41(12): 2346-2352.
［3］赵洪华, 陈鸣, 魏镇韩. 层析成像技术中的自适应网络拓扑推断算法［J］. 西安电子科技大学学报, 2009, 36(3): 547-552.
Zhao Honghua, Chen Ming, Wei Zhenhan. Self Adaptive Network Topology Inference Algorithm in Tomography［J］. Journal of Xidian University, 2009, 36(3): 547-552.
［4］ Castro R, Coates M, Nowak R. Likelihood Based Hierarchical Clustering ［J］. IEEE Transactions on Signal Processing, 2004, 52(8): 2308-2321.
［5］ Shih M, Hero A. Hierarchical Inference of Unicast Network Topologies Based on End-to-End Measurements ［J］. IEEE Transactions on Signal Processing, 2007, 55(5): 1708-1718.
［6］ Fei G, Hu G. Improving Maximum-likelihood-based Topology Inference by Sequentially Inserting Leaf Nodes［J］. IET Communications, 2011, 5(15): 2221-2230.
［7］ Ni J, Xie H, Tatikonda S, et al. Efficient and Dynamic Routing Topology Inference from End-to-End Measurements ［J］. IEEE／ACM Transactions on Networking, 2010, 18(1): 123-135.
［8］ Eriksson B, Dasarathy G, Barford P, et al. Efficient Network Tomography for Internet Topology Discovery［J］. IEEE／ACM Transactions on Networking, 2012, 20(3): 931-943.
［9］于林森, 张田文. 用于图像分割的滤波EM算法［J］. 计算机学报, 2006, 29(6): 928-935.
Yu Linsen, Zhang Tianwen. Filtering EM Algorithm for Image Segmentation［J］. Chinses Journal of Computers, 2006, 29(6): 928-935.
［10］王戈, 于宏毅, 沈智翔, 等. 一种基于EM算法的快速收敛参数估计方法［J］. 吉林大学学报(工学版), 2013, 43(2): 532-537.
Wang Ge, Yu Hongyi, Shen Zhixiang, et al. Fast Convergence Parameter Estimation Method Based on Expectation-maximum Algorithm［J］. Journal of Jilin University(Engineering and Technology Edtion), 2013, 43(2): 532-537.

利用有限混合模型的高效网络拓扑推断算法

Efficient topology inference algorithm using the finite mixture model

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 10